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

本题为查询树的深度，我们采用直接遍历二叉树，并记录我们访问深度的方法即可。

可以考虑用一个全局变量记录我们的深度，也可以通过DFS函数每一次返回当前子树的深度。

若采用返回值，则有

当前树长度 = max(左子树深度, 右子树深度) + 1

计算二叉树的深度，简单的前序遍历即可。
递归算法：

点击(此处)折叠或打开

/**
 * 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