110. 平衡二叉树

题目:https://leetcode-cn.com/problems/balanced-binary-tree/

代码:

class Solution {

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int lh = getHeight(root.left);
        int rh = getHeight(root.right);
        if (Math.abs(lh - rh) <= 1 && isBalanced(root.left) && isBalanced(root.right)) {
            return true;
        }
        return false;
    }

    /**
     * 获取树的高度
     * @param node
     * @return
     */
    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int lh = getHeight(node.left);
        int rh = getHeight(node.right);
        return Math.max(lh, rh) + 1;
    }

}

思路:

题目中对高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1

那我们的就从树的高度入手,我们写一个方法用来获取某个节点的树高度(递归调用,节点为null则认为高度为0,否则高度为左右子树高度的最大值+1)。获取树的高度的方法实现之后,题目就迎刃而解,按照题目的要求写条件即可。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助,欢迎给作者打赏