[LeetCode 104]Maximum Depth of Binary Tree (easy)

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example
Given a binary tree as follow:

  1
 / \ 
2   3
   / \
  4   5
The maximum depth is 3.

思路1. Top-down

1. 递归函数maintain2个变量，1) current depth 2) maxDepth.
2. Base Case：

• 当前节点为空时，直接返回
• 如果节点为leaf, 用current depth更新maxDepth

3. 继续递归其左右子节点，current depth + 1 传入左右子树。

思路2. Bottom-up

1. 递归函数直接返回current max depth.
2. Base Case：

• 当前节点为空时，直接返回0

3. leftDepth = maxDepth (root.left);
rightDepth = maxDepth(root.right);。
4. return Math.max (leftDepth, rightDepth) + 1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**************  Top down solution *******************/
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int[] maxDepth = { Integer.MIN_VALUE };
        
        maxDepthHelper (root, 1, maxDepth);
        
        return maxDepth[0];
    }
    
    private void maxDepthHelper (TreeNode root, int depth, int[] maxDepth) {
        if (root == null) {
            return;
        }
        
        if (root.left == null && root.right == null) {
            maxDepth[0] = Math.max (maxDepth[0], depth);
            return;
        }
        
        maxDepthHelper (root.left, depth + 1, maxDepth);
        maxDepthHelper (root.right, depth + 1, maxDepth);
    }
    
    /********************** Top Down End*********************/
    
    
        
    /**************  Bottom Up solution *******************/
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return maxDepthHelper (root);
    }
    
    private int maxDepthHelper (TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftDepth = maxDepthHelper (root.left);
        int rightDepth = maxDepthHelper (root.right);
        
        return Math.max (leftDepth, rightDepth) + 1;
    }
    /**************  Bottom Up END *******************/
}