题目

如果一个节点X，它左树结构和右树结构完全一样
那么我们说以X为头的树是相等树
给定一棵二叉树的头节点head
返回head整棵树上有多少棵相等子树

一、暴力解

以x为头的整颗树有多少颗相等子树
可能性
1)左树上有多少颗相等子树+右树上有多少颗相等子树,验证自己是不是相等子树,需要验证左树的结构是否等于右树的结构
定义函数same:你给我一个节点h1,再给我节点h2,告诉你h1的结构跟h2结构相不相等。
整体调用递归sum函数:以x为头的整颗树有多少颗相等子树

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }

    // 时间复杂度O(N * logN)
    public static int sameNumber1(Node head) {
        if (head == null) {
            return 0;
        }
        return sameNumber1(head.left) + sameNumber1(head.right) + (same(head.left, head.right) ? 1 : 0);
    }
    //判断两颗子树是否是否相等
    public static boolean same(Node h1, Node h2) {
        if (h1 == null ^ h2 == null) {
            return false;
        }
        if (h1 == null && h2 == null) {
            return true;
        }
        // 两个都不为空
        return h1.value == h2.value && same(h1.left, h2.left) && same(h1.right, h2.right);
    }

复杂度

最差的情况,数字都是1
如果这棵树特别不平衡,验证的行为就很少
越平衡,这个方法复杂度越差
用master公式: O(N"logN)

二、子树序列化优化

想把左树跟右树比对这个过程将复杂度O(N)-->0(1)
二叉树的先序序列化把一个结构信息变成一个字符串信息这个字符串信息就代表我结构本身
字符串做hash成一个固定长度的哈希值
空认为是#,变成一个hashcode:a12f3
发现节点2的左树,右树hashcode相等==>2是相等子树节点
2怎么加工自己的这棵树的hashcode?
a12f3_2_a12f3调用hashB数--> b25cb
用hashcode拼接后继续做hashcode,
这样左树右树的信息都是一个固定长度的字符串, hashcode虽然比较长,但是不会超过一个固定长度所以这样就把一个O(N)的比对行为变成了O(1)了

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }
    public static int sameNumber2(Node head) {
        String algorithm = "SHA-256";
        Hash hash = new Hash(algorithm);
        return process(head, hash).ans;
    }

    public static class Info {
        public int ans;
        public String str;

        public Info(int a, String s) {
            ans = a;
            str = s;
        }
    }
    public static Info process(Node head, Hash hash) {
        if (head == null) {
            return new Info(0, hash.hashCode("#,"));
        }
        Info l = process(head.left, hash);
        Info r = process(head.right, hash);
        int ans = (l.str.equals(r.str) ? 1 : 0) + l.ans + r.ans;
        String str = hash.hashCode(String.valueOf(head.value) + "," + l.str + r.str);
        return new Info(ans, str);
    }