二叉树的最大深度 & n叉树的最大深度
这道题前几天用迭代法做了一遍，今天试着用递归法做，其实稀里糊涂的给蒙出来了。
class Solution {
public:
int depth(TreeNode* cur, int dep){
if(cur == nullptr){
return dep;
}
return max(depth(cur->left,dep+1),depth(cur->right,dep+1));
}
int maxDepth(TreeNode* root) {
int res = 0;
if(root==nullptr)
return res;
res= max(depth(root->left,1),depth(root->right,1));
return res;
}
};
之后又稀里糊涂的把n叉树的最大深度写了出来。其实很大程度上是碰上的成分。我觉得还得看一遍Carl的视频加深一下。自己写的问题还是有一些不懂的，比如我之前把cur_dep设成了INT_MIN，结果就不对了。但是设成0就可以了。
class Solution {
public:
int travesal(Node* cur, int depth){
if(cur == nullptr){
return depth;
}
int cur_dep = 0;
for(int i=0; i<cur->children.size(); i++){
int temp_depth = travesal(cur->children[i],depth);
cur_dep = max(temp_depth,cur_dep);
cout<<temp_depth<<endl;
}
return cur_dep+1;
}
int maxDepth(Node* root) {
if(root == nullptr){
return 0;
}
int res = travesal(root,1);
return res;
}
};
二叉树的最小深度
想了半天怎么用递归法做这道题，虽然说想到了一些容易踩到的陷阱，比如不能粗暴的min() 就像上一题一样求出来最小深度，因为那样的话，保留最小值就这能是0。刚才在上一道题Carl讲过说求深度用前序，求高度用后序。我就想着试着用后序来做这道题，但参考上一题，后序还涉及到回溯算法，我就放弃了，有点太难了。
这么一比，虽然迭代法写起来不怎么简洁，但是通俗易懂。最后照着Carl的答案写了一遍。没完全理解，还得再做几遍才行。 这道题我前几天写过迭代法的版本。迭代法需要注意的就是只有在当前node的左右子节点都为nullptr的时候，才算是遍历到了其中的一个根。
class Solution {
public:
int res;
void depth(TreeNode* cur, int dep){
if((cur->left == nullptr) && (cur->right == nullptr)){
res = min(res,dep);
return;
}
if(cur->left != nullptr){
depth(cur->left,dep+1);
}
if(cur->right != nullptr){
depth(cur->right,dep+1);
}
return ;
}
int minDepth(TreeNode* root) {
res = INT_MAX;
if(root == nullptr){
return 0;
}
depth(root,1);
return res;
}
};
完全二叉树的节点个数
今天真是稀里糊涂写出四道题答案的一天。。。又蒙对一道题。
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == nullptr){
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
看了Carl用完全二叉树的的特性来专门写的一种方法，有点绕。就是把这一整颗二叉树递归成小二叉树，然后再计算 2^树深度 - 1 来算出一共有有多少个节点。
