win10使用dw做网站,小说网站80电子书怎么做,seo入门培训学校,wordpress文章链接带问号代码随想录 | Day17 | 二叉树#xff1a;二叉树的最大深度最小深度
主要学习内容#xff1a;
利用前序后序层序求解二叉树深度问题
其中穿插回溯法
104.二叉树的最大深度
104. 二叉树的最大深度 - 力扣#xff08;LeetCode#xff09;
递归遍历
后序遍历 …代码随想录 | Day17 | 二叉树二叉树的最大深度最小深度
主要学习内容
利用前序后序层序求解二叉树深度问题
其中穿插回溯法
104.二叉树的最大深度
104. 二叉树的最大深度 - 力扣LeetCode
递归遍历
后序遍历
1.递归函数参数和返回值
使用后序遍历一般都是上层需要使用下层函数的返回值
本道题目是返回值表示该子树的最大深度所以为int
函数参数就是当前结点
int r(TreeNode *t)2.确定终止条件
遇到空指针说明结束这层函数
if(tnullptr)return 0;3.本层逻辑
定义上
返回值是这棵子树的最大深度
所以记录左右子树的最大深度然后取最大值再加上本层就是自身的最大深度然后返回即可 int leftr(t-left);int rightr(t-right);int res1max(left,right);return res;完整代码
class Solution {
public:int r(TreeNode *t){if(tnullptr)return 0;int leftr(t-left);int rightr(t-right);int res1max(left,right);return res;}int maxDepth(TreeNode* root) {return r(root);}
}; class Solution {
public:int r(TreeNode *t){if(tnullptr)return 0;return 1max(r(t-left),r(t-right));}int maxDepth(TreeNode* root) {return r(root);}
}; 前序遍历
其实就是回溯法
1.确定函数参数和返回值
不需要返回值参数就是当前节点记录最大值由全局变量完成函数参数也可以完成两者等价
2.终止条件
如果当前节点左右孩子都为空说明深度就到这里为止了
3.本层处理逻辑
就是遍历本层的结点这是二叉树所以只有左右孩子两个用两个if来表示遍历即可
如果做过回溯篇会知道应该此处对应是for循环
然后左不为空深度继续遍历函数结束后还原现场
然后右边一样 if(t-left){res;r(t-left);res--;}if(t-right){res;r(t-right);res--;}完整代码
class Solution {
public:int res,result;void r(TreeNode *t){if(t-leftnullptrt-rightnullptr){resultmax(res,result);return;}if(t-left){res;r(t-left);res--;}if(t-right){res;r(t-right);res--;}}int maxDepth(TreeNode* root) {res1;result0;if (root NULL) return result;r(root);return result;}
}; 层序遍历
还是套用之前的模板就行不做过多的赘述
559.N叉树的最大深度
559. N 叉树的最大深度 - 力扣LeetCode
后序遍历
和刚刚思路一模一样模仿着写就行
class Solution {
public:int r(Node *t){int depth0;if(tnullptr)return 0;for(auto c:t-children){int resr(c);depthmax(depth,res1);}return depth;}int maxDepth(Node* root) {if(rootnullptr)return 0;return r(root)1;}
};前序遍历
也和前面一样差别就是前面是左右子树而这里是for循环
class Solution {
public:int res;void r(Node *t,int depth){resmax(depth,res);for(auto c:t-children)r(c,depth1);}int maxDepth(Node* root) {if(rootnullptr)return 0;res0;r(root,1);return res;}
};层序遍历
也还是套模板就行
111.二叉树最小深度
111. 二叉树的最小深度 - 力扣LeetCode
后序遍历
和最大深度的区别就是左孩子为空右孩子不为空和左不为空右为空的逻辑处理剩下的都一样
class Solution {
public:int r(TreeNode *t){if (t nullptr) return 0;int leftr(t-left);int rightr(t-right);//左为空右不为空 返回右边最小深度1if(t-leftnullptrt-right!nullptr)return right1;//左不为空右为空 返回左边最小深度1if(t-left!nullptrt-rightnullptr)return left1;int res1min(left,right);return res;}int minDepth(TreeNode* root) {if(rootnullptr)return 0;return r(root);}
};前序遍历
和之前一模一样
class Solution {
public:int res;void r(TreeNode *t,int depth){if(t-rightnullptrt-leftnullptr){resmin(depth,res);return;}if(t-left){depth;r(t-left,depth);depth--;}if(t-right){depth;r(t-right,depth);depth--;}}int minDepth(TreeNode* root) {if(rootnullptr)return 0;res0x3f3f3f3f;r(root,1);return res;}
};
