首页 > 编程语言 >代码随想录算法训练营第十六天 | 104.二叉树的最大深度、559.n叉树的最大深度，111.二叉树的最小深度，222.完全二叉树的节点个数

代码随想录算法训练营第十六天 | 104.二叉树的最大深度、559.n叉树的最大深度，111.二叉树的最小深度，222.完全二叉树的节点个数

时间：2023-02-01 09:44:05浏览次数：61  
标签：node right TreeNode val int 随想录 二叉树 深度 left

Day15 周日休息~

一、参考资料

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

题目链接/文章讲解/视频讲解： 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

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

题目链接/文章讲解/视频讲解：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

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

题目链接/文章讲解/视频讲解：https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html

二、LeetCode104.二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。 
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14. // version1：递归法 —— 根节点的高度就是二叉树的最大深度
  15.     int getdepth(TreeNode* node) {
  16.         if (node == NULL) return 0;
  17.         int leftdepth = getdepth(node->left);   // 左
  18.         int rightdepth = getdepth(node->right); // 右
  19.         int depth = max(leftdepth, rightdepth) + 1;
  20.         return depth;
  21.     }
  22.     int maxDepth(TreeNode* root) {
  23.         return getdepth(root);
  24.     }
  25. };
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14. // version2：递归法 —— 根节点的高度就是二叉树的最大深度(简化版)
  15.     int maxDepth(TreeNode* root) {
  16.         if (root == NULL) return 0;
  17.         return 1 + max(maxDepth(root->left), maxDepth(root->right));
  18.     }
  19. };
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14. // version1和version2采用的均为后序遍历（左右中），当然也可以通过前序遍历（中左右）实现
  15. // version3：递归法 —— 前序遍历，充分表现深度回溯的过程
  16.     int result;
  17.     void getdepth(TreeNode* node, int depth) {
  18.         result = depth > result ? depth : result;  // 中
  19.         if (node->left == NULL && node->right == NULL) return;
  20.         // 左
  21.         if (node->left) {
  22.             depth++;    // 深度+1
  23.             getdepth(node->left, depth);
  24.             depth--;    // 回溯，深度-1
  25.         }
  26.         // 右
  27.         if (node->right) {
  28.             depth++;
  29.             getdepth(node->right, depth);
  30.             depth--;
  31.         }
  32.         return ;
  33.     }
  34.  
  35.     int maxDepth(TreeNode* root) {
  36.         if (root == NULL) return 0;
  37.         getdepth(root, 1);
  38.         return result;
  39.     }
  40. };
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14. // version4：递归法 —— 前序遍历，充分表现深度回溯的过程(简化代码)
  15.     int result;
  16.     void getdepth(TreeNode* node, int depth) {
  17.         result = depth > result ? depth : result;  // 中
  18.         if (node->left == NULL && node->right == NULL) return;
  19.         // 左
  20.         if (node->left) {
  21.             getdepth(node->left, depth + 1);
  22.         }
  23.         // 右
  24.         if (node->right) {
  25.             getdepth(node->right, depth + 1);
  26.         }
  27.         return ;
  28.     }
  29.  
  30.     int maxDepth(TreeNode* root) {
  31.         if (root == NULL) return 0;
  32.         getdepth(root, 1);
  33.         return result;
  34.     }
  35. };
  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     // version5: 迭代法
  15.     int maxDepth(TreeNode* root) {
  16.         queue<TreeNode*> que;
  17.         int depth = 0;
  18.         if (root == NULL) return 0;
  19.         que.push(root);
  20.         while(!que.empty()) {
  21.             int size = que.size();
  22.             depth++;
  23.             for (int i = 0; i < size; i++) {
  24.                 TreeNode* node = que.front();
  25.                 que.pop();
  26.                 if (node->left) que.push(node->left);
  27.                 if (node->right) que.push(node->right);
  28.             }
  29.         }
  30.         return depth;
  31.     }
  32. };

三、LeetCode559.n叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/description/

示例1：

示例2：

给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

示例 1：（如上图）
输入：root = [1,null,3,2,4,null,5,6] 输出：3
示例 2：（如上图）
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：5
提示:
树的深度不会超过 1000 。
树的节点数目位于 [0, 104] 之间。 
  1. // 递归法
  2. /*
  3. // Definition for a Node.
  4. class Node {
  5. public:
  6.     int val;
  7.     vector<Node*> children;
  9.     Node() {}
  11.     Node(int _val) {
  12.         val = _val;
  13.     }
  15.     Node(int _val, vector<Node*> _children) {
  16.         val = _val;
  17.         children = _children;
  18.     }
  19. };
  20. */
  21.  
  22. class Solution {
  23. public:
  24.     int maxDepth(Node* root) {
  25.         if (root == NULL) return 0;
  26.         int depth = 0;
  27.         for (int i = 0; i < root->children.size(); i++) {
  28.             depth = max (depth, maxDepth(root->children[i]));
  29.         }
  30.         return depth + 1;
  31.     }
  32. };
  1. // 迭代法
  2. /*
  3. // Definition for a Node.
  4. class Node {
  5. public:
  6.     int val;
  7.     vector<Node*> children;
  9.     Node() {}
  11.     Node(int _val) {
  12.         val = _val;
  13.     }
  15.     Node(int _val, vector<Node*> _children) {
  16.         val = _val;
  17.         children = _children;
  18.     }
  19. };
  20. */
  21.  
  22. class Solution {
  23. public:
  24.     int maxDepth(Node* root) {
  25.         queue<Node*> que;
  26.         if (root != NULL) que.push(root);
  27.         int depth = 0;
  28.         while (!que.empty()) {
  29.             int size = que.size();
  30.             depth++;
  31.             for (int i = 0; i < size; i++) {
  32.                 Node* node = que.front();
  33.                 que.pop();
  34.                 for (int j = 0; j < node->children.size(); j++) {
  35.                     if (node->children[j]) que.push(node->children[j]);
  36.                 }
  37.             }
  38.         }
  39.         return depth;        
  40.     }
  41. };

四、LeetCode111.二叉树的最小深度

https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

示例1：

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

示例 1：（如上图）
输入：root = [3,9,20,null,null,15,7] 输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6] 输出：5

提示：
树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000 
  1. // 递归法
  2. /**
  3.  * Definition for a binary tree node.
  4.  * struct TreeNode {
  5.  *     int val;
  6.  *     TreeNode *left;
  7.  *     TreeNode *right;
  8.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  10.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     int getDepth(TreeNode* node) {
  16.         if (node == NULL) return 0;
  17.         int leftDepth = getDepth(node->left);
  18.         int rightDepth = getDepth(node->right);
  19.  
  20.         // 当一个左子树为空，右不为空，这时并不是最低点
  21.         if (node->left == NULL && node->right != NULL) {
  22.             return 1 + rightDepth;
  23.         }
  24.  
  25.         // 当一个左子树不为空，右为空，这时并不是最低点
  26.         if (node->left != NULL && node->right == NULL) {
  27.             return 1 + leftDepth;
  28.         }
  29.         
  30.         int result = 1 + min(leftDepth, rightDepth);
  31.         return result;
  32.     }
  33.  
  34.     int minDepth(TreeNode* root) {
  35.         return getDepth(root);
  36.     }
  37. };
  1. // 简化版递归法
  2. /**
  3.  * Definition for a binary tree node.
  4.  * struct TreeNode {
  5.  *     int val;
  6.  *     TreeNode *left;
  7.  *     TreeNode *right;
  8.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  10.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     int minDepth(TreeNode* root) {
  16.         if (root == NULL) return 0;
  17.         if (root->left == NULL && root->right != NULL) {
  18.             return 1 + minDepth(root->right);
  19.         }
  20.         if (root->left != NULL && root->right == NULL) {
  21.             return 1 + minDepth(root->left);
  22.         }
  23.         return 1 + min(minDepth(root->left), minDepth(root->right));
  24.     }
  25. };
  1. // 迭代法
  2. /**
  3.  * Definition for a binary tree node.
  4.  * struct TreeNode {
  5.  *     int val;
  6.  *     TreeNode *left;
  7.  *     TreeNode *right;
  8.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  10.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     int minDepth(TreeNode* root) {
  16.         int depth = 0;
  17.         queue<TreeNode*> que;
  18.         if (root == NULL) return 0;
  19.         que.push(root);
  20.         while (!que.empty()) {
  21.             int size = que.size();
  22.             depth++;
  23.             for (int i = 0; i < size; i++) {
  24.                 TreeNode* node = que.front();
  25.                 que.pop();
  26.                 if (node->left) que.push(node->left);
  27.                 if (node->right) que.push(node->right);
  28.                 if (!node->left && !node->right){
  29.                     return depth;
  30.                 }
  31.             }
  32.         }
  33.         return depth;
  34.     }
  35. };

五、LeetCode222.完全二叉树的节点个数

https://leetcode.cn/problems/count-complete-tree-nodes/description/

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

示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
示例 2：
输入：root = [] 输出：0
示例 3：
输入：root = [1] 输出：1
提示：
树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是 完全二叉树 
  1. // 递归法
  2. /**
  3.  * Definition for a binary tree node.
  4.  * struct TreeNode {
  5.  *     int val;
  6.  *     TreeNode *left;
  7.  *     TreeNode *right;
  8.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  10.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     int getNodesSum(TreeNode* cur) {
  16.         if (cur == NULL) return 0;
  17.         int leftNum = getNodesSum(cur->left);
  18.         int rightNum = getNodesSum(cur->right);
  19.         int treeNum = leftNum + rightNum + 1;
  20.         return treeNum;
  21.     }
  22.     int countNodes(TreeNode* root) {
  23.         return getNodesSum(root);
  24.     }
  25. };
  1. // 简化版递归法
  2. /**
  3.  * Definition for a binary tree node.
  4.  * struct TreeNode {
  5.  *     int val;
  6.  *     TreeNode *left;
  7.  *     TreeNode *right;
  8.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  10.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     int countNodes(TreeNode* root) {
  16.         if (root == NULL) return 0;
  17.         return 1 + countNodes(root->left) + countNodes(root->right);
  18.     }
  19. };
  1. // 迭代法
  2. /**
  3.  * Definition for a binary tree node.
  4.  * struct TreeNode {
  5.  *     int val;
  6.  *     TreeNode *left;
  7.  *     TreeNode *right;
  8.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  10.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  11.  * };
  12.  */
  13. class Solution {
  14. public:
  15.     int countNodes(TreeNode* root) {
  16.         queue<TreeNode*> que;
  17.         int result = 0;
  18.         if (root != NULL) que.push(root);
  19.         while (!que.empty()) {
  20.             int size = que.size();
  21.             for (int i = 0; i < size; i++) {
  22.                 TreeNode* node = que.front();
  23.                 que.pop();
  24.                 result++;
  25.                 if (node->left) que.push(node->left);
  26.                 if (node->right) que.push(node->right);
  27.             }
  28.         }
  29.         return result;
  30.     }
  31. };

总结：

递归的三要素在写之前需要先想明白，另外，由于先完成“层序遍历”的缘故，反而对于迭代法的写法更加熟练，还要多回顾哈！

刷题加油鸭~~

标签：node,right,TreeNode,val,int,随想录,二叉树,深度,left
From： https://www.cnblogs.com/ucaszym/p/17081549.html

相关文章

  • [数据结构] 根据前中后序遍历中的两种构造二叉树
    前中后序遍历前中后序遍历的特点前序遍历前序遍历顺序：根节点->左子树->右子树前序遍历结果：[根节点，[左子树前序遍历结果]，[右子树前序遍历结果]]假如把前序遍历结果......
  • 代码随想录(2)-链表
    题单203.移除链表元素链表节点对象publicclassListNode{//结点的值intval;//下一个结点ListNodenext;//节点的构造函数(无参)......
  • 代码随想录算法训练营第35天
    今日刷题3道：455.分发饼干，376.摆动序列，53.最大子序和● 455.分发饼干https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.htmlclassSo......
  • 二叉树最大深度
    //leetcodesubmitregionbegin(Prohibitmodificationanddeletion)/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*......
  • OpenYurt v1.2 新版本深度解读（一）: 聚焦边云网络优化
    本文作者：李志信，OpenYurtMember，ApachedubboPMC，专注于云原生边缘计算的系统架构和解决方案张逸飞，OpenYurtMember，浙江大学SEL实验室云原生边缘计算智能开源平台CN......
  • 代码随想录算法训练营第十六天|LeetCode 104. 二叉树的最大深度、LeetCode 111.二叉树
    104.二叉树的最大深度文章：代码随想录(programmercarl.com)视频：二叉树的高度和深度有啥区别？究竟用什么遍历顺序？很多录友搞不懂|LeetCode：104.二叉树的最大深度_哔哩哔......
  • BM25 二叉树的后序遍历
    https://www.nowcoder.com/practice/1291064f4d5d4bdeaefbf0dd47d78541?tpId=295&tqId=2291301&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2......
  • BM24 二叉树的中序遍历
    https://www.nowcoder.com/practice/0bf071c135e64ee2a027783b80bf781d?tpId=295&tqId=1512964&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%......
  • 114. 二叉树展开为链表
    问题描述https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/解题思路这个题目，用一个数组就能很好的解决。但空间复杂度是O(n).题目中给的......
  • 掌握hashtable，深度理解python字典的数据结构
    文章目录​​1.hash函数​​​​2.hashtable​​​​2.1链地址法实现hashtable​​​​2.2解决冲突​​​​2.3开放寻址法实现hashtable​​​​2.4逻辑删除key​​​......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99