【LeetCode】平衡二叉树

#LeetCode每日一题【二叉树专题】

• 平衡二叉树
  https://leetcode-cn.com/problems/balanced-binary-tree/
• 分析
  平衡二叉树的定义：
  每个节点的左右两个子树的高度差的绝对值不超过 1，即满足平衡二叉树左右子树都是平衡二叉树，且左右子树的高度差绝对值不超过1；
  当求一棵树的高度时，使用dfs递归的时候，知道左右子树的高度的同时也是可以判断这棵树是否平衡，如果有一颗子树不平衡，则整棵树不平衡。
• 实现

public boolean isBalanced(TreeNode root) {
        // 不等于-1，即平衡（且返回值是树的高度）
        return height(root) != -1;
    }

    // 既然这个方法返回树的高度，那同时也是可以判断该树是否是平衡二叉树的
    // 灵活变通一下，当这棵树不平衡的时候直接返回-1（即高度差>1），其中一个字树不平衡，其树肯定不平衡
    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = heightOptimize(root.left);
        int right = heightOptimize(root.right);

        // 其中一颗树不平衡，即返回-1，不平衡
        if (left == -1 || right == -1) {
            return -1;
        }
        // 高度差大于1，不平衡
        if (Math.abs(left - right) > 1) {
            return -1;
        }
        // 正常，平衡返回其高度
        return Math.max(left, right) + 1;
    }

LeetCode耗时：0ms

• 总结

当求一棵树的高度时，使用dfs递归的时候，知道左右子树的高度的同时也是可以判断这棵树是否平衡，如果有一颗子树不平衡，则整棵树不平衡