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

【算法刷题day16】Leetcode:104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

news 来源：原创 2024/5/16 22:43:30

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

文档链接：[代码随想录]
题目链接：104.二叉树的最大深度（优先掌握递归）
状态：ok

题目：
给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
注意：
1.暂时只看了递归的方法没有看迭代法
2.后序遍历会比前序遍历简单

class Solution {
public:int maxDepth(TreeNode* root) {int max = getDepth(root);return max;}int getDepth(TreeNode* root){if(root == NULL)return 0;int leftDepth = getDepth(root -> left);int rightDepth = getDepth(root -> right);int maxDepth = 1 + max(leftDepth, rightDepth);return maxDepth;}
};

class solution {
public:int result;void getdepth(TreeNode* node, int depth) {result = depth > result ? depth : result; // 中if (node->left == NULL && node->right == NULL) return ;if (node->left) { // 左depth++;    // 深度+1getdepth(node->left, depth);depth--;    // 回溯，深度-1}if (node->right) { // 右depth++;    // 深度+1getdepth(node->right, depth);depth--;    // 回溯，深度-1}return ;}int maxDepth(TreeNode* root) {result = 0;if (root == NULL) return result;getdepth(root, 1);return result;}
};

559.n叉树的最大深度

题目链接：559.n叉树的最大深度


class Solution {
public:int maxDepth(Node* root) {if(root == NULL)return 0;int depth = 0;for(int i = 0; i < root -> children.size(); i++){depth = max(depth, maxDepth(root -> children[i]));}return depth + 1;}
};

111.二叉树的最小深度

文档链接：[代码随想录]
题目链接：111.二叉树的最小深度
状态：ok

题目：
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
注意：
两边的子树分开求最小值

class Solution {
public:int minDepth(TreeNode* root) {return min(root);}int min(TreeNode* root){if(root == NULL) return 0;int leftDepth = min(root -> left);int rightDepth = min(root -> right);if(root -> left == NULL && root -> right != NULL){return 1 + rightDepth;}if(root -> right == NULL && root -> left != NULL){return 1 + leftDepth;}int result = 1 + std::min(leftDepth, rightDepth);return result;}
};

222.完全二叉树的节点个数

文档链接：[代码随想录]
题目链接：111.二叉树的最小深度
状态：ok

题目：
给你一棵完全二叉树的根节点 root ，求出该树的节点个数。
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

class Solution {
public:int countNodes(TreeNode* root) {return count(root);}int count(TreeNode* node){if(node == NULL) return 0;int leftNum = count(node -> left);int rightNum = count(node -> right);int cou = leftNum + rightNum + 1;return cou;}
};