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.
题目很简单，但考的很基础。二叉树的遍历方式有两种：递归和非递归，本题也有两种解法。
计算二叉树的深度，简单的前序遍历即可。
递归算法：

/**
 * 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) {
        int depth = 0;
        if(root != null){
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            depth ++;
            if(leftDepth < rightDepth){
                depth = depth + rightDepth;
            }else{
                depth = depth + leftDepth;
            }
        }
        return depth;
    }
}

非递归算法：
受后续遍历二叉树思想的启发，想到可以利用后续遍历的方法来求二叉树的深度，在每一次输出的地方替换成算栈S的大小，遍历结束后最大的栈S长度即是栈的深度。
算法的执行步骤如下：
（1）当树非空时，将指针p指向根节点，p为当前节点指针。
（2）将p压入栈S中，0压入栈tag中，并令p执行其左孩子。
（3）重复步骤（2），直到p为空。
（4）如果tag栈中的栈顶元素为1，跳至步骤（6）。从右子树返回
（5）如果tag栈中的栈顶元素为0，跳至步骤（7）。从左子树返回
（6）比较treedeep与栈的深度，取较大的赋给treedeep，对栈S和栈tag出栈操作，p指向NULL，并跳至步骤（8）。
（7）将p指向栈S栈顶元素的右孩子，弹出栈tag，并把1压入栈tag。（另外一种方法，直接修改栈tag栈顶的值为1也可以）
（8）循环（2）~（7），直到栈为空并且p为空
（9）返回treedeep，结束遍历

int TreeDeep(BinTree BT ){
    int treedeep=0;
    stack S;
    stack tag;
    BinTree p=BT;
    while(p!=NULL||!isEmpty(S)){
        while(p!=NULL){
            push(S,p);
            push(tag,0);
            p=p->lchild;
        }
        if(Top(tag)==1){
            deeptree=deeptree>S.length?deeptree:S.length;
            pop(S);
            pop(tag);
            p=NULL;
        }else{
            p=Top(S);
            p=p->rchild;
            pop(tag);
            push(tag,1);
        }
    }
    return deeptree;
}

前序、中序、和后序遍历的递归和非递归实现，参考博文：
http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html