JZ55 二叉树的深度

二叉树的深度_牛客题霸_牛客网

递归代码太简单-一行就可以,可以用二叉树的层序遍历，顺便温习下二叉树层序遍历的写法。

对应leetcode 104题，层序遍历对应leetcode-102自顶向下，leetcode-107自底向上

/*
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;// int depthLeft = TreeDepth(pRoot->left);// int depthRight = TreeDepth(pRoot->right);// return (depthLeft>depthRight)?(depthLeft+1):(depthRight+1);//层次遍历求树的深度// return pRoot? 1+max(TreeDepth(pRoot->left), TreeDepth(pRoot->right)): 0;//递归一行代码搞定if(!pRoot)return 0;TreeNode *pCur = pRoot, *plast = pRoot,*prelast = pRoot;queue<TreeNode*>treeQueue;int level_cnt = 0;treeQueue.push(pCur);while(!treeQueue.empty()){pCur = treeQueue.front();if(pCur->left){treeQueue.push(pCur->left);plast = pCur->left;}if(pCur->right){treeQueue.push(pCur->right);plast = pCur->right;}// treeQueue.pop();if(prelast == pCur){ //prelast=pCur的时候，plast始终指向pCur下一层的最右结点++level_cnt;prelast = plast;//更新prelast}treeQueue.pop();}return level_cnt;}
};