544，剑指 Offer-平衡二叉树
Time goes on and on, never to an end but crossings.
时间一直走，没有尽头，只有路口。
问题描述
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的高度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3/ \9 20/ \15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1/ \2 2/ \3 3/ \4 4
返回 false 。
限制：
0 <= 树的结点个数 <= 10000
从上到下
平衡二叉树要求的是左右子节点的高度不能超过1，所以我们可以判断树的左右两个子节点的高度只要不超过1就行，而树的高度怎么计算呢，其实很简单，代码如下
1//计算树中节点的高度
2public int depth(TreeNode root) {
3 if (root == null)
4 return 0;
5 return Math.max(depth(root.left), depth(root.right)) + 1;
6}
所以这题的代码我们也很容易写出来
1public boolean isBalanced(TreeNode root) {
2 if (root == null)
3 return true;
4 //分别计算左子树和右子树的高度
5 int left = depth(root.left);
6 int right = depth(root.right);
7 //这两个子树的高度不能超过1
8 return Math.abs(left - right) <= 1;
9}
10
11//计算树中节点的高度
12public int depth(TreeNode root) {
13 if (root == null)
14 return 0;
15 return Math.max(depth(root.left), depth(root.right)) + 1;
16}
但这里会有个问题，因为二叉平衡树的任何一棵子树也都必须是平衡的，上面我们只判断了根节点的两个子节点的高度是否小于等于1，没有判断子树是否是平衡的。
如下图所示，虽然根节点的两个子节点的高度是一样的，但很明显根节点的右子树不是平衡的，也就是说这棵树不是平衡二叉树。
所以除了判断根节点以外，还需要判断所有的子节点，具体看下视频
再来看下代码
1public boolean isBalanced(TreeNode root) {
2 if (root == null)
3 return true;
4 //分别计算左子树和右子树的高度
5 int left = depth(root.left);
6 int right = depth(root.right);
7 //这两个子树的高度不能超过1，并且他的两个子树也必须是平衡二叉树
8 return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
9}
10
11//计算树中节点的高度
12public int depth(TreeNode root) {
13 if (root == null)
14 return 0;
15 return Math.max(depth(root.left), depth(root.right)) + 1;
16}
从下到上
上面的计算过程是从上往下判断的，其实我们还可以从下往上判断，就是从叶子节点开始往上，如果某一个子树不是平衡的就返回false，具体看视频
先判断两个子树是否是平衡的，然后再判断以当前节点为根节点的子树是否是平衡的……。来看下代码
1//如果等于-1就表示不是平衡的
2private static final int UNBALANCED = -1;
3
4public boolean isBalanced(TreeNode root) {
5 return helper(root) != UNBALANCED;
6}
7
8public int helper(TreeNode root) {
9 if (root == null)
10 return 0;
11
12 //如果左子节点不是平衡二叉树，直接返回UNBALANCED
13 int left = helper(root.left);
14 if (left == UNBALANCED)
15 return UNBALANCED;
16
17 //如果右子节点不是平衡二叉树，直接返回UNBALANCED
18 int right = helper(root.right);
19 if (right == UNBALANCED)
20 return UNBALANCED;
21
22 //如果左右子节点都是平衡二叉树，但他们的高度相差大于1，
23 //直接返回UNBALANCED
24 if (Math.abs(left - right) > 1)
25 return UNBALANCED;
26
27 //否则就返回二叉树中节点的最大高度
28 return Math.max(left, right) + 1;
29}
总结
关于二叉树的一些常用术语我们来总结一下：
节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点度称为树的度；
叶节点或终端节点：度为零的节点；
非终端节点或分支节点：度不为零的节点；
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
堂兄弟节点：父节点在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林；
●
●
●
●