Balanced Binary Tree

https://leetcode.com/problems/balanced-binary-tree/description/

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Thoughts

看到二叉树先想分治。这道题和上道题的区别在于不只是记录深度，还要进行比较。 直接的想法是用两次分治，外层判断isBalanced, isBalanced内部再用分治算depth。 但这么做会重复计算树的深度，时间复杂度O(n^2). 此时我们可以对depth()进行特殊处理，让它在算深度时判断是否balanced, 如果不balance直接返回-1。 因为我们的目标不是计算深度，而是只要有imbalanced就返回即可。

Code

class Solution {

    private int depth(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = depth(node.left);
        int right = depth(node.right);

        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }

        return Math.max(left, right) + 1;
    }

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (depth(root) == -1) {
            return false;
        } else {
            return true;
        }
    }

}

Analysis

一次分治遍历: O(n)

Ver.2

用stack帮助遍历, 用map记录每个遇到过的节点它的子树最大深度.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        Map<TreeNode, Integer> map = new HashMap<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if ((node.left == null || node.left != null && map.containsKey(node.left)) 
               && (node.right == null || node.right != null && map.containsKey(node.right))) {
                int left = node.left == null ? 0 : map.get(node.left);
                int right = node.right == null ? 0 : map.get(node.right);
                if (Math.abs(left - right) > 1) {
                    return false;
                }
                map.put(node, Math.max(left, right) + 1);
            } else {
                if (node.left != null && !map.containsKey(node.left)) {
                    stack.push(node);
                    stack.push(node.left);
                } else {
                    stack.push(node);
                    stack.push(node.right);
                }
            }
        }
        return true;
    }
}