Leetcode: Maximum Depth of Binary Tree

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.

Understand of the problem:
The problem asks for finding the maximum depth of a binary tree. The maximum depth is defined as the number of nodes along the longest path from the root down to the farthest leaf node. 

Recursive Solution:
The idea is still using pre-order traversal. We keep tracking of the depth of each node, and if the node is a leaf, we compare its depth with the maximum depth, and update the maximum depth, if needed. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int max = Integer.MIN_VALUE;
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        maxDepth(root, 0);
        
        return max;
    }
    
    private void maxDepth(TreeNode root, int depth) {
        if (root == null) return;
        
        depth++;
        
        // check if it is leaf
        if (root.left == null && root.right == null && depth > max) {
            max = depth;
        }
        
        maxDepth(root.left, depth);
        maxDepth(root.right, depth);
    }
}

Post-order Traversal Solution:
So far I think we have been very familiar with the pre-order traversal. For this problem, we can also do the post-order traversal of the binary tree, i.e, traverse from bottom-up. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        return Math.max(left, right) + 1;
    }
}

Post-order Iterative Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        int max = 0;
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> depthStack = new Stack<Integer>();
        
        TreeNode prev = null;
        nodeStack.push(root);
        depthStack.push(1);
        
        while (!nodeStack.empty()) {
            TreeNode curr = nodeStack.peek();
            int depth = depthStack.peek();
            
            if (prev == null || curr == prev.left || curr == prev.right) {
                if (curr.left != null) {
                    nodeStack.push(curr.left);
                    depthStack.push(depth + 1);
                } else if (curr.right != null) {
                    nodeStack.push(curr.right);
                    depthStack.push(depth + 1);
                } else {
                    nodeStack.pop();
                    depthStack.pop();
                    if (depth > max) max = depth;
                }
            } else if (prev == curr.left) {
                if (curr.right != null) {
                    nodeStack.push(curr.right);
                    depthStack.push(depth + 1);
                } else {
                    nodeStack.pop();
                    depthStack.pop();
                    if (depth > max) max = depth;
                }
            } else if (prev == curr.right) {
                nodeStack.pop();
                depthStack.pop();
                if (depth > max) max = depth;
            }
            
            prev = curr;
        }
        return max;
    }
}

Summary:
The problem itself is very simple, but do be familiar with the post-order traversal. Especially be careful about the return value and how it works. 

Update on 9/30/14:
DFS solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int max = 0;
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        maxDepthHelper(root, 0);
        
        return max;
    }
    
    private void maxDepthHelper(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        
        depth++;
        
        if (root.left == null && root.right == null) {
            if (depth > max) {
                max = depth;
            }
            return;
        }
        
        maxDepthHelper(root.left, depth);
        maxDepthHelper(root.right, depth);
    }
}

Divide-and-Conquer

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        
        if (root == null) {
            return 0;
        }
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        return Math.max(left, right) + 1;
    }
}