Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

平衡二叉树

Posted on In ,
Symbols count in article: 1.1k Reading time ≈ 1 mins.

来源Leetcode第110题平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回 true 。

自底向上的递归

这道题和求树的高度是一样的，只是在递归求解的时候需要判断树的左右高度是否是平衡的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
boolean flag = true;
public boolean isBalanced(TreeNode root) {
    if(root == null)
        return true;
    hlper(root);
    return flag;
}

public int hlper(TreeNode root){
    int height_l = 0,height_r = 0;
    if(root.left != null)
        height_l = 1 + hlper(root.left);
    if(root.right != null)
        height_r = 1 + hlper(root.right);
    if(Math.abs(height_l - height_r) > 1)
        flag = false;
    return Math.max(height_l,height_r);
}

分支 - 限界

当递归求解出现左右子树高度相差大于1的情况时，记返回值为-1，这样遇到-1，就可以一路返回上一层，避免了多余的计算。
来自题解

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
public boolean isBalanced(TreeNode root) {
        //-1 即为存在层数相差大于1
		return depth(root)!=-1;
	}

	/**
	 * 以当前节点为根节点的树的层数
	 * 返回-1的话说明 不满足要求不用求了直接 -1 退出
	 * @param root
	 * @return
	 */
	private static int depth(TreeNode root){
        //当前节点不存在其层数为0
		if(root==null) return 0;
        //获取左节点的层数
		int left = depth(root.left);
        //如果层数为-1直接截断
		if(left==-1)return -1;
        //获取右节点的层数
		int right = depth(root.right);
		//如果层数为-1直接退出
        if(right==-1)return  -1;
		//如果左右节点层数相差大于1 直接返回-1 否则返回真实层数
        return Math.abs(left-right)<2?Math.max(left,right)+1:-1;
	}