二叉树深度递归与非递归

/*
struct TreeNode {
int val;
struct TreeNode left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};/
二叉树递归即是分治的思想，和归并排序类似
二叉树的深度递归计算即是在回溯过程中计算，每一次回溯都去左右子树的最大值
可以将一颗二叉树想成一个根节点和两颗左右整体子树，最后的结果肯定是左右子树的高度取最大值+1

二叉树非递归即是借助于队列的思想，和层次遍历类似
每一次必须把每一层的结点都出队后才能使高度+1，直到队空返回level高度即可
class Solution {
public:
//递归
int TreeDepth(TreeNode* pRoot)
{
if (pRoot == NULL) return 0;

    int leftnum = TreeDepth(pRoot -> left);
    int rightnum = TreeDepth(pRoot -> right);

    return (leftnum > rightnum ? leftnum : rightnum) + 1;
}
//非递归
int TreeDepth(TreeNode* pRoot)
{
    if (!pRoot) return 0;
    queue<TreeNode*> Q;
    Q.push(pRoot);
    int level = 0;
    while (!Q.empty())
    {
        int sz = Q.size();
        while (sz --)
        {
            auto node = Q.front(); Q.pop();
            if (node -> left) Q.push(node -> left);
            if (node -> right) Q.push(node -> right);
        }
        level++;
    }
    return level;
}

};