明显的dfs，可以用递归、栈做

递归自底向上计数节点个数的思路值得记住，不需要传额外的参数，利用返回值即可，也就不需要helper函数了

/**
 * 自己的代码1
 * 递归做dfs
 * Runtime: 0 ms, faster than 100.00% 
 * Memory Usage: 39.1 MB, less than 32.27%
 */
class Solution {
    public int maxDepth(TreeNode root) {
        return helper(root, 0);
    }
    private int helper(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        sum++;
        if (root.left == null && root.right == null) {
            return sum;
        }
        return Math.max(helper(root.left, sum), helper(root.right, sum));
    }
}

/**
 * 自己的代码2
 * 栈做dfs
 * Runtime: 1 ms, faster than 12.13%
 * Memory Usage: 38.5 MB, less than 93.86%
 */
class Solution {
    public int maxDepth(TreeNode root) {
        int res = 0;
        if (root == null) {
            return res;
        }
        Stack<TreeNode> s = new Stack<>();
        root.val = 1;
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode curr = s.pop();
            if (curr.left == null && curr.right == null) {
                res = Math.max(res, curr.val);
            }
            if (curr.left != null) {
                curr.left.val = curr.val + 1;
                s.push(curr.left);
            }
            if (curr.right != null) {
                curr.right.val = curr.val + 1;
                s.push(curr.right);
            }
        }
        return res;
    }
}

/**
 * discuss里的，巨简洁dfs递归代码
 * 自底向上从0开始计数节点个数
 * 空节点返回0，其他节点在左右子树返回值较大者的基础上，加1就是自身到叶子节点的最大长度
 * Runtime: 0 ms, faster than 100.00%
 * Memory Usage: 38.7 MB, less than 74.37% 
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}