L1-平衡二叉树

Posted on | In |

平衡二叉树
给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。

1
2
3
4
5
6
7
8
9
样例
给出二叉树 A={3,9,20,#,#,15,7}, B={3,#,20,15,7}

A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7
二叉树A是高度平衡的二叉树，但是B不是

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if this Binary tree is Balanced, or false.
     */
    public boolean isBalanced(TreeNode root) 
    {
        if(root == null)
            return true;
        // write your code here
        int left=maxHeight(root.left);
        int right=maxHeight(root.right);
        if(Math.abs(left-right)>1)
        return false;
        else 
        return isBalanced(root.left)&&isBalanced(root.right);
        //注意不是return true; 必须每个节点都平衡
    }
    public int maxHeight(TreeNode root)
    {
        if(root==null) return 0;
      int  h_left=maxHeight(root.left)+1;
       int h_right=maxHeight(root.right)+1;
        int ma=Math.max(h_left,h_right);
        System.out.println(ma);
        return ma;
    }
}

思路

先求左子树和右子树的最大深度，然后判断是否相差大于1，如果是，则不可能是，如果相差小于，继续递归调用判断左子树和右子树是否都是平衡二叉树。

参考链接
https://www.jiuzhang.com/solutions/balanced-binary-tree/