rafactor: isBalanced tree

dairongpeng · dairongpeng · commit 23dcdac8162c · 2022-02-21T22:46:35.000+08:00
diff --git a/08-二叉树递归解题思路.md b/08-二叉树递归解题思路.md
@@ -1,21 +1,20 @@
 [TOC]
-# 1 二叉树的递归套路
+# 1 二叉树的递归解法
 
 1、 可以解决面试中的绝大部分二叉树(95%以上)的问题，尤其是树形dp问题
 
 2、 其本质是利用递归遍历二叉树的便利性，每个节点在递归的过程中可以回到该节点3次
 
 
-==具体步骤为：==
-
+具体步骤为：
 1. 假设以X节点为头，假设可以向X左树和右树要任何信息
 2. 在上一步的假设下，讨论以X为头结点的树，得到答案的可能性（最重要），常见分类是与X无关的答案，与X有关的答案
 3. 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
 4. 把左树信息和右树信息求全集，就是任何一颗子树都需要返回的信息S
 5. 递归函数都返回S，每颗子树都这么要求
 6. 写代码，在代码中考虑如何把左树信息和右树信息整合出整棵树的信息
 
-## 1.1 二叉树的递归套路深度实践
+## 1.1 二叉树的递归解法实操
 
 ### 1.1.1 例一：判断二叉树平衡与否
 
@@ -27,112 +26,55 @@
 
 > 所以该题，我们X需要向左右子树要的信息为，1.高度 2. 是否平衡
 
-```Java
-package class08;
-
-public class Code01_IsBalanced {
-
-	public static class Node {
-		public int value;
-		public Node left;
-		public Node right;
-
-		public Node(int data) {
-			this.value = data;
-		}
-	}
-
-	public static boolean isBalanced1(Node head) {
-		boolean[] ans = new boolean[1];
-		ans[0] = true;
-		process1(head, ans);
-		return ans[0];
-	}
-
-	public static int process1(Node head, boolean[] ans) {
-		if (!ans[0] || head == null) {
-			return -1;
-		}
-		int leftHeight = process1(head.left, ans);
-		int rightHeight = process1(head.right, ans);
-		if (Math.abs(leftHeight - rightHeight) > 1) {
-			ans[0] = false;
-		}
-		return Math.max(leftHeight, rightHeight) + 1;
-	}
-
-	public static boolean isBalanced2(Node head) {
-		return process2(head).isBalaced;
-	}
-
-	// 左、右要求一样，Info 表示信息返回的结构体
-	public static class Info {
-	        // 是否平衡
-		public boolean isBalaced;
-		// 高度多少
-		public int height;
+```Go
+package main
 
-		public Info(boolean b, int h) {
-			isBalaced = b;
-			height = h;
-		}
-	}
+import "math"
 
-        // 递归调用，X自身也要返回信息Info。
-        // 解决X节点(当前节点)怎么返回Info信息
-	public static Info process2(Node X) {
-	        // base case
-		if (X == null) {
-			return new Info(true, 0);
-		}
-		// 得到左树信息
-		Info leftInfo = process2(X.left);
-		// 得到右树信息
-		Info rightInfo = process2(X.right);
-		
-		// 高度等于左右最大高度，加上当前头结点的高度1
-		int height = Math.max(leftInfo.height, rightInfo.height) + 1;
-		boolean isBalanced = true;
-		// 左树不平衡或者右树不平衡，或者左右两子树高度差超过1
-		// 那么当前节点为头的树，不平衡
-		if (!leftInfo.isBalaced || !rightInfo.isBalaced || Math.abs(leftInfo.height - rightInfo.height) > 1) {
-			isBalanced = false;
-		}
-		// 加工出当前节点的信息返回
-		return new Info(isBalanced, height);
-	}
+type Node struct {
+	Val int
+	Left *Node
+	Right *Node
+}
 
-	// for test
-	public static Node generateRandomBST(int maxLevel, int maxValue) {
-		return generate(1, maxLevel, maxValue);
-	}
+// BalanceInfo 表示递归过程中需要收集每个节点的信息
+type BalanceInfo struct {
+	// 当前节点为头的树是不是平衡的
+	IsBalanced bool
+	// 当前节点为头的树的高度是多少
+	Height int
+}
 
-	// for test
-	public static Node generate(int level, int maxLevel, int maxValue) {
-		if (level > maxLevel || Math.random() < 0.5) {
-			return null;
-		}
-		Node head = new Node((int) (Math.random() * maxValue));
-		head.left = generate(level + 1, maxLevel, maxValue);
-		head.right = generate(level + 1, maxLevel, maxValue);
-		return head;
-	}
+// IsBalanced 给定二叉树头节点，判断该二叉树是不是平衡二叉树
+func (head *Node) IsBalanced() bool {
+	return Process(head).IsBalanced
+}
 
-	public static void main(String[] args) {
-		int maxLevel = 5;
-		int maxValue = 100;
-		int testTimes = 1000000;
-		for (int i = 0; i < testTimes; i++) {
-			Node head = generateRandomBST(maxLevel, maxValue);
-			if (isBalanced1(head) != isBalanced2(head)) {
-				System.out.println("Oops!");
-			}
-		}
-		System.out.println("finish!");
+func Process(node *Node) *BalanceInfo {
+	if node == nil {
+		return &BalanceInfo{
+			IsBalanced: true,
+			Height:     0,
+		}
+	}
+	// 左子树信息
+	leftInfo := Process(node.Left)
+	// 右子树信息
+	rightInfo := Process(node.Right)
+	// 高度等于左右最大高度，加上当前头结点的高度1
+	curHeight := int(math.Max(float64(leftInfo.Height), float64(rightInfo.Height))) + 1
+	curIsBalanced := true
+	// 左树不平衡或者右树不平衡，或者左右两子树高度差超过1
+	// 那么当前节点为头的树，不平衡
+	if !leftInfo.IsBalanced || !rightInfo.IsBalanced || math.Abs(float64(leftInfo.Height) -float64(rightInfo.Height)) > 1 {
+		curIsBalanced = false
+	}
+	// 加工出当前节点的信息返回
+	return &BalanceInfo{
+		IsBalanced: curIsBalanced,
+		Height:     curHeight,
 	}
-
 }
-
 ```
 
 ### .1.2 例二：返回二叉树任意两个节点最大值
