剑指offer编程题—二叉树的深度

题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解题思路1
递归思想，很简单，不用解释了。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        return pRoot? max(TreeDepth(pRoot->left),TreeDepth(pRoot->right))+1:0;
    }
};

解题思路2
层次遍历树的思想，每遍历完树的一层，树的深度+1,因此需要添加一个标志用于表示每一层的结束。这里的思想其实就是之前做的题把二叉树打印成多行的思想。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if(!pRoot) return 0;
        queue<TreeNode*> q;
        int count=0;
        TreeNode* flag=NULL;
        q.push(pRoot);
        q.push(flag); //标识第一行的结尾
        TreeNode* tmp;
        while(!q.empty()){
            tmp=q.front();
            q.pop();
            if(tmp==flag){
                ++count;
                if(q.empty()) break; //这里的判断很有必要，没有这句会陷入死循环。q.empty()成立即代表已经到最后一层的结尾标识了，应该跳出循环。
                q.push(flag); //当前层遍历完成后，下一层也就是当前层的孩子节点已经都在队列中了，因此添加层结尾标识
            }
            else{
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
        }
        return count;
    }
};