package com.binaryTree;

import com.binaryTree.zuo.Hash;

public class LeftRightSameTreeNumber {


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

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

    // 如果一个节点X，它左树结构和右树结构完全一样，那么我们说以X为头的子树是相等子树
    // 给定一棵二叉树的头节点head，返回head整棵树上有多少棵相等子树
    public static int sameNumber1(Node head) {
        if (head == null){
            return 0;
        }
        return sameNumber1(head.left) + sameNumber1(head.right) + (isSame(head.left,head.right) ? 1: 0);
    }

    public static boolean isSame(Node h1,Node h2){
        // 异或运算 ^,无进位相加 false -> 0,true -> 1, 或相同为false，不同为true
        if (h1 == null ^ h2 == null){
            return false;
        }
        if (h1 == null && h2 == null){
            return true;
        }
        return h1.value == h2.value && isSame(h1.left,h2.left) && isSame(h1.right,h2.right);
    }

    // 时间复杂度O(N)，哈希函数：同样的输入 可以保证相同 的输出。
    //  使用哈希函数，二叉树序列化 后形成的长字符串将会形成固定长度的摘要，会仅有极小的概率发生歧义
    //  需要复习二叉树的序列化
    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);
    }

    public static Node randomBinaryTree(int restLevel, int maxValue) {
        if (restLevel == 0) {
            return null;
        }
        Node head = Math.random() < 0.2 ? null : new Node((int) (Math.random() * maxValue));
        if (head != null) {
            head.left = randomBinaryTree(restLevel - 1, maxValue);
            head.right = randomBinaryTree(restLevel - 1, maxValue);
        }
        return head;
    }

    public static void main(String[] args) {
        int maxLevel = 8;
        int maxValue = 4;
        int testTime = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            Node head = randomBinaryTree(maxLevel, maxValue);
            int ans1 = sameNumber1(head);
            int ans2 = sameNumber2(head);
            if (ans1 != ans2) {
                System.out.println("出错了！");
                System.out.println(ans1);
                System.out.println(ans2);
            }
        }
        System.out.println("测试结束");

    }

}