day19-二叉树的最大最小深度

二叉树的最大/最小深度

给定一个二叉树 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。

而递归的逻辑是：我们需要在根节点的左子树和右子树中选最大值，所以这里用max（x,y）返回。

当递归到空节点开始返回，一开始返回0，后面逐渐+1…，到根节点就得到这颗子树的高度。

层序遍历

class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*> qu;if(root != nullptr)qu.push(root);else return 0;int ans = 0;while(!qu.empty()){int size = qu.size();for(int i=0;i<size;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_left+m_right+1:min(m_right,m_left)+1;}
};

层序遍历

相比递归，BFS要简单的多，我们只需要找到第一个叶子节点，然后返回即可，找不到，没关系，继续遍历下一层。

class Solution {
public:int minDepth(TreeNode* root) {queue<TreeNode*> qu;if(root != nullptr)qu.push(root);else return 0;int ans = 1;while(!qu.empty()){int size = qu.size();for(int i=0;i<size;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。