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 is3.

1.divide and conquer

分左和分右计算递归次数，base case 是root == null 这时return 0 并开始计算

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
    public int maxDepth(TreeNode root) {
        // write your code here
        if (root == null) {
            return 0;
        }
        int leftSum = maxDepth(root.left);
        int rightSum = maxDepth(root.right);

        return Math.max(leftSum + 1, rightSum + 1);
    }
}

1. Traversal

需要一个instance variable记录递归中的sum change, 随时比较当前的depth 和总depth, 注意如果只有一个node 的情况

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */

    private int depth; 

    public int maxDepth(TreeNode root) {
        // write your code here
        depth = 0;
        maxDepthHelper(1, root);
        return depth;
    }

    public void maxDepthHelper(int curDepth, TreeNode root) {
        if (root == null) {
            return;
        }

        if (curDepth > depth) {
            depth = curDepth;
        }

        maxDepthHelper(curDepth + 1, root.left);
        maxDepthHelper(curDepth + 1, root.right);
    }
}