AcWing 71. 二叉树的深度
原题链接
简单
作者:
二叉树专题绝赞攻克中
,
2023-11-20 21:50:24
,
所有人可见
,
阅读 60
错误:1.处理break条件 2.写成了if(!tmp->left)好多判断条件写反了,鉴定为写太久脑袋写昏了
明天来补充深度优先遍历怎么写~
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int treeDepth(TreeNode* root) {
//深度优先遍历--每次都记录长度,然后最后再比较--用vector或者两两比较
//应该用宽度优先搜索-->因为是一层一层走的,而且是最小值
if(!root) return 0;
queue<TreeNode*> q;
int cnt=0;
q.push(root);
q.push(nullptr);//每行用null分割
vector<int> level;
while(q.size()){
TreeNode* tmp=q.front();
q.pop();
if(!tmp){
cnt++;
// if(!q.size()) break;//不添加这句话,会导致反复加上nullptr然后一直在循环,这句话加的位置不对
q.push(nullptr);
// cout << "here---";
if(q.front()==nullptr && tmp==nullptr) break;
continue;
}
// cout << "tmp的值" <<tmp->val<<endl;
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
return cnt;
}
// void dfs(TreeNode* subroot){
// if(!subroot){
// // res=max(res,tmp);
// res.push_back(tmp);
// tmp=0;
// return;
// }//不行,因为左右节点都可能为空
// //还是不行,因为函数的递归调用会使累加很乱,会出现半途置0的情况导致记录有误
// // tmp++;
// dfs(subroot->left);
// dfs(subroot->right);
// }
// void dfs(TreeNode* root){
// }
};