当前位置：首页 > news >正文

day16二叉树part03 | 104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

news 来源：原创 2024/9/29 23:35:22

104.二叉树的最大深度（优先掌握递归）

两种思路：
1.使用递归，主要思想是递归遍历左右子树，然后左右子树高度的最大值加1即为当前节点的高度
2.之前学习层次遍历的时候做过这题，直接在层次遍历的时候加上一个计数变量即可

思路1，递归法

class Solution {
public:// 1.首先确定函数参数和返回值，要返回的是一个intint depth(TreeNode* root) {// 2.这是终止条件if (root == nullptr) return 0;// 3.单层计算的逻辑int llen = depth(root->left);int rlen = depth(root->right);return max(llen, rlen) + 1;}int maxDepth(TreeNode* root) {return depth(root);}
};

思路2，层次遍历

class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*> que;int length = 0;if (root != nullptr) que.push(root);while (!que.empty()){int size = que.size();length++;for (int i = 0; i < size; i++){TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return length;}
};

题目链接/文章讲解/视频讲解： https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html

111.二叉树的最小深度（优先掌握递归）

递归法

class Solution {
public:int depth(TreeNode* root) {if (root == nullptr) return 0;int llen, rlen;llen = depth(root->left);rlen = depth(root->right);// 如果左孩子为空，右孩子不空if (!root->left && root->right) return 1+rlen;// 如果右孩子为空，左孩子不空if (root->left && !root->right) return 1+llen;return 1+min(llen, rlen);}int minDepth(TreeNode* root) {return depth(root);}
};

层次遍历法


class Solution {
public:int minDepth(TreeNode* root) {queue<TreeNode*> que;int length = 0;if (root != nullptr) que.push(root);while (!que.empty()){int size = que.size();length++;for (int i = 0; i < size; i++){TreeNode* node = que.front();que.pop();if (!node->left && !node->right)return length;if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return length;}
};

题目链接/文章讲解/视频讲解：https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html

222.完全二叉树的节点个数（优先掌握递归）

class Solution {
public:int count(TreeNode* node) {if (node == nullptr) return 0;int leftnum = count(node->left);int rightnum = count(node->right);return leftnum + rightnum + 1;}int countNodes(TreeNode* root) {return count(root);}
};