参考 https://leetcode.cn/problems/balanced-binary-tree/solution/balanced-binary-tree-di-gui-fang-fa-by-jin40789108/

剪枝

判定是不是平衡二叉树，只有有一个子树不是那么就可以判定这棵树不是平衡二叉树。也就是说，只要出现了false，就没必要再去检查其他子树。

这是我的写法

public static boolean isBalanced(TreeNode root) {if(root==null) return true;return ss(root,0)>0;}
public static int ss(TreeNode node,int i){if(node==null){return i;}int m = ss(node.left,i+1);int n = ss(node.right,i+1);if(Math.abs(m-n)>1||m<0||n<0){return -1;}else{return Math.max(m,n);}}

这是标准答案

class Solution {public boolean isBalanced(TreeNode root) {return recur(root) != -1;}private int recur(TreeNode root) {if (root == null) return 0;int left = recur(root.left);if(left == -1) return -1;int right = recur(root.right);if(right == -1) return -1;return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;}
}

这两种唯一的区别就是出口，标准答案是提前返回了，而我写的是在处理完左右子树之后才返回，标准答案完成了剪枝。

在上面这种情况下，标答可以剪去红色部分。

---

另外信息时自底向上汇聚的，在返回的同时，将信息也返回了。而不是单独再去计算这个节点的深度，下面这个就是非自底向上。

class Solution {public boolean isBalanced(TreeNode root) {if (root == null) return true;return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);}private int depth(TreeNode root) {if (root == null) return 0;return Math.max(depth(root.left), depth(root.right)) + 1;}
}