空包网站怎么建设,网站代理加盟赚钱吗,深圳招聘网站哪个好,jsp网站建设毕业设计二叉树的最大/最小深度
给定一个二叉树 root #xff0c;返回其最大/小深度。
二叉树的 最大/小深度 是指从根节点到最远/近叶子节点的最长路径上的节点数。
思路
求最大深度比较简单#xff0c;我们先解决最大深度。
最大深度
递归
class Solution {
public:int maxD…二叉树的最大/最小深度
给定一个二叉树 root 返回其最大/小深度。
二叉树的 最大/小深度 是指从根节点到最远/近叶子节点的最长路径上的节点数。
思路
求最大深度比较简单我们先解决最大深度。
最大深度
递归
class Solution {
public:int maxDepth(TreeNode* root) {if(root null)return 0;return max(maxDepth(root-left),maxDepth(root-right))1;}
};非常简单的一句代码。但是理解起来却有点难度。
终止条件为root null时返回0。
想一想当结点为空时此时高度是不存在的因此返回0。
而递归的逻辑是我们需要在根节点的左子树和右子树中选最大值所以这里用maxx,y返回。
当递归到空节点开始返回一开始返回0后面逐渐1…到根节点就得到这颗子树的高度。
层序遍历
class Solution {
public:int maxDepth(TreeNode* root) {queueTreeNode* qu;if(root ! nullptr)qu.push(root);else return 0;int ans 0;while(!qu.empty()){int size qu.size();for(int i0;isize;i){TreeNode* node qu.front();qu.pop();if(node-left ! nullptr)qu.push(node-left);if(node-right ! nullptr)qu.push(node-right);}ans;}return ans;}
};这里用的是层序遍历也即是广度优先对每一层的结点进行遍历然后同时ans
其实最大深度就是求的最大高度因此有多少层可以遍历即高度多少。
最小深度
递归
当root为空则当前高度为0当root的左右子节点均为空则当前为叶子结点高度为1如果左右子节点有一个为空则m_left和m_right必有一个为0则直接返回两者相加1最后一种情况则是左右子节点均不为空则返回左右子树深度小的
class Solution {
public:int minDepth(TreeNode* root) {if(root nullptr)return 0;if(root-left nullptr root-right nullptr)return 1;int m_left minDepth(root-left);int m_right minDepth(root-right);return root-left nullptr || root-right nullptr ?m_leftm_right1:min(m_right,m_left)1;}
};层序遍历
相比递归BFS要简单的多我们只需要找到第一个叶子节点然后返回即可找不到没关系继续遍历下一层。
class Solution {
public:int minDepth(TreeNode* root) {queueTreeNode* qu;if(root ! nullptr)qu.push(root);else return 0;int ans 1;while(!qu.empty()){int size qu.size();for(int i0;isize;i){TreeNode* cur qu.front();qu.pop();if(cur-left nullptr cur-right nullptr){return ans;}if(cur-left ! nullptr)qu.push(cur-left);if(cur-right ! nullptr)qu.push(cur-right);}ans;}return ans;}
};注意的是ans一开始初始化为1是因为根节点自身便带有高度只有空结点会为0。
