110.平衡二叉树，两个递归

linwt · linwt · commit 1c5fd38f3fe0 · 2022-04-10T23:18:16.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -46,6 +46,7 @@
 103. 二叉树的锯齿形层序遍历
 104. 二叉树的最大深度
 105. 从前序与中序遍历序列构造二叉树
+110. 平衡二叉树
 114. 二叉树展开为链表
 115. 不同的子序列
 121. 买卖股票的最佳时机
diff --git a/leetcode_Java/Solution0110.java b/leetcode_Java/Solution0110.java
@@ -0,0 +1,49 @@
+// 110. 平衡二叉树
+
+
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode() {}
+ *     TreeNode(int val) { this.val = val; }
+ *     TreeNode(int val, TreeNode left, TreeNode right) {
+ *         this.val = val;
+ *         this.left = left;
+ *         this.right = right;
+ *     }
+ * }
+ */
+
+
+/*
+剑指offer 39.平衡二叉树
+1、本题需要两个递归方法，一个是递归计算每个节点的深度，一个是递归判断每个节点是否平衡
+2、递归计算节点深度
+  1）方法功能：入参是一个节点，返回该节点的深度
+  2）终止条件：节点为空时返回0
+  3）递归逻辑：左右节点同样需要计算深度，因此调用同样的方法
+  4）返回值：节点的深度 = 1 + max(左节点深度, 右节点深度)
+3、递归判断每个节点是否平衡
+  1）方法功能：入参是一个节点，返回该节点的左右子树是否平衡
+  2）终止条件：节点为空时返回true
+  3）递归逻辑：调用计算深度的方法得到左右节点的深度，计算高度差是否不超过1，是则平衡返回true，否则不平衡返回false。左右节点同样需要判断是否平衡，因此调用同样的方法
+  4）返回值：
+ */
+class Solution {
+    public boolean isBalanced(TreeNode root) {
+        if (root == null) {
+            return true;
+        }
+        return Math.abs(treeDepth(root.left) - treeDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
+    }
+
+    private int treeDepth(TreeNode root) {
+        if (root == null) {
+            return 0;
+        }
+        return 1 + Math.max(treeDepth(root.left), treeDepth(root.right));
+    }
+}
diff --git a/剑指Offer_Java/Test39.java b/剑指Offer_Java/Test39.java
@@ -6,16 +6,16 @@ public boolean IsBalanced_Solution(TreeNode root) {
         if (root == null) {
             return true;
         }
-        if (Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) > 1) {
+        if (Math.abs(treeDepth(root.left) - treeDepth(root.right)) > 1) {
             return false;
         }
         return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
     }
 
-    public int TreeDepth(TreeNode root) {
+    public int treeDepth(TreeNode root) {
         if (root == null) {
             return 0;
         }
-        return 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
+        return 1 + Math.max(treeDepth(root.left), treeDepth(root.right));
     }
 }

Original file line number	Diff line number	Diff line change
`@@ -6,16 +6,16 @@ public boolean IsBalanced_Solution(TreeNode root) {`
`6`	`6`	`if (root == null) {`
`7`	`7`	`return true;`
`8`	`8`	`}`
`9`		`- if (Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) > 1) {`
	`9`	`+ if (Math.abs(treeDepth(root.left) - treeDepth(root.right)) > 1) {`
`10`	`10`	`return false;`
`11`	`11`	`}`
`12`	`12`	`return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);`
`13`	`13`	`}`
`14`	`14`
`15`		`- public int TreeDepth(TreeNode root) {`
	`15`	`+ public int treeDepth(TreeNode root) {`
`16`	`16`	`if (root == null) {`
`17`	`17`	`return 0;`
`18`	`18`	`}`
`19`		`- return 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));`
	`19`	`+ return 1 + Math.max(treeDepth(root.left), treeDepth(root.right));`
`20`	`20`	`}`
`21`	`21`	`}`