Min/Max/Balanced Depth

• 一个树 depth 的定义是，最深处 node 的 depth，所以要取 max.

Maximum Depth of Binary Tree

public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;

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

Minimum Depth of Binary Tree

一个意思，不过注意拐弯处如果缺了一个 child 并不代表是 valid path，因为这个节点可能不是 leaf node.

public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;

        if(root.left == null) return minDepth(root.right) + 1;
        if(root.right == null) return minDepth(root.left) + 1;

        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

Balanced Binary Tree

已经不平衡的地方就直接 return -1 ，避免去进一步做不必要的递归。

public class Solution {
    public boolean isBalanced(TreeNode root) {
        return (getDepth(root) != -1);
    }

    private int getDepth(TreeNode root){
        if(root == null) return 0;

        int left = getDepth(root.left);
        int right = getDepth(root.right);

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

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