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("测试结束");

 }

}