110.平衡二叉树.md

110. 平衡二叉树

url

题目

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

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

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

输入：root = [3,9,20,null,null,15,7]
输出：true
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
输入：root = []
输出：true

方法

可递归，当然也可迭代

• 其实就是抓着平衡二叉树的定义作为判断：个节点的左右两个子树的高度差的绝对值不超过1

code

js

let res = true;
let isBalanced = root => {
    depth(root);
    return res;
}
let depth = root => {
    if (root === null) return 0;
    let l = depth(root.left);
    let r = depth(root.right);
    if (Math.abs(l - r) > 1) res = false;
    return 1 + Math.max(l, r);
}

go

func isBalanced(root *TreeNode) bool {
	var res = true
	var depth func (root *TreeNode) int
	Max := func(a int, b int) int {
		if a < b {
			return b
		} else {
			return a
		}
	}
	depth = func (root *TreeNode) int {
		if root == nil {
		return 0
	}
		l := depth(root.Left)
		r := depth(root.Right)
		if Abs(l - r) > 1{
		res = false
	}
		return 1 + Max(l, r)
	}
	depth(root)
	return res
}

java

class Solution {
    private boolean res = true;
    public boolean isBalanced(TreeNode root) {
        Depth(root);
        return res;
    }
    private int Depth (TreeNode root) {
        if (root == null) return 0;
        int l = Depth(root.left);
        int r = Depth(root.right);
        if (Math.abs(l - r) > 1) res = false;;
        return 1 + Math.max(l , r);
    }
}