# 力扣刷题 Day16 - 104.111.222

**Published by:** [Monkey船长](https://paragraph.com/@monkey-9/)
**Published on:** 2023-03-31
**URL:** https://paragraph.com/@monkey-9/day16-104-111-222

## Content

今天（3.31）依旧在补昨天的任务，实际上这几天都是这样的模式。 二叉树部分开始后有点放弃了思考，读完题面就去看题解，意识到这样子下去只会把题目水过去而已。为什么要刷题？我希望通过这个过程可以去锻炼自己的思维，以后遇到题目可以知道如何思考，更进一步希望可以教给学生如何思考。这和今天在 科技爱好者周刊（第 248 期）：不要夸大 ChatGPT - 阮一峰的网络日志 中看到的学习微积分的一段话带给我的思考一致。你学习微积分，不是因为要在日常生活中使用，而是因为它让你的思维变得更强大。今天三道题目，我改为了先自己尝试去思考和写代码，然后再去看题解。虽然三道题目我都只是用广搜队列着同一个方法一遍 AC，但每次 AC 的感觉依旧很爽。 看题解视频提到的递归遍历的方法对我还是不够熟悉的存在。经过三道题目递归遍历的洗礼，似乎有点掌握到递归的思路是什么，之后的题目要限定自己——先尝试看看递归如何去写。104. 二叉树的最大深度104. 二叉树的最大深度 - 力扣（Leetcode）问题分析二叉树节点的深度指从根节点到该节点的最长简单路径边的条数或者节点数二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数后者节点数 根节点的高度就是二叉树的最大深度，可以用后序遍历求根节点高度，也可用前序遍历直接求深度。通过前序遍历，逻辑是先求得左右节点高度，在二者较大值基础上加一即为根结点高度。代码实现后序遍历求高度class Solution { public: int getDepth(TreeNode* node) { if (node == nullptr) return 0; int left_depth = getDepth(node->left); int right_depth = getDepth(node->right); int depth = 1 + max(left_depth, right_depth); return depth; } int maxDepth(TreeNode* root) { return getDepth(root); } }; 广搜队列class Solution { public: int maxDepth(TreeNode* root) { queue<TreeNode*> que; int ans = 0; if (root == nullptr) return ans; que.push(root); while (!que.empty()) { int size = que.size(); ans++; while (size--) { TreeNode* node = que.front(); que.pop(); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } } return ans; } }; 111. 二叉树的最小深度111. 二叉树的最小深度 - 力扣（Leetcode）问题分析和上面的「104. 二叉树的最大深度」几乎一样，稍微改动即可。代码实现后序遍历实现class Solution { public: int getDepth(TreeNode* node) { if (node == nullptr) return 0; int left_depth = getDepth(node->left); int right_depth = getDepth(node->right); if (node->left == nullptr && node->right) return 1 + right_depth; if (node->right == nullptr && node->left) return 1 + left_depth; return 1 + min(left_depth, right_depth); } int minDepth(TreeNode* root) { return getDepth(root); } }; 广搜队列class Solution { public: int minDepth(TreeNode* root) { int result = 0; queue<TreeNode*> que; if (root == nullptr) return result; que.push(root); while (!que.empty()) { int size = que.size(); result++; while (size--) { TreeNode* node = que.front(); if (!node->left && !node->right) return result; que.pop(); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } } return result; } }; 222. 完全二叉树的节点个数222. 完全二叉树的节点个数 - 力扣（Leetcode）问题分析如果是一棵满二叉树，若深度为 kk，则其共有 2k−12^k-1 个节点。这道题目在完全二叉树的前提下，判断子树是否为满二叉树，若是则直接利用公式计算。实际上不断递归下去必然是一颗满二叉树，因为只有一个节点就是一棵满二叉树 ![[Leetcode-cn 222. 完全二叉树的节点个数-1.png]] 判断满二叉树的方法：检测向左和向右遍历后其深度是否相等代码实现利用满二叉树节点公式class Solution { public: int countNodes(TreeNode* root) { if (root == nullptr) return 0; TreeNode* left = root->left; TreeNode* right = root->right; int left_depth = 0, right_depth = 0; while (left) { left = left->left; left_depth++; } while (right) { right = right->right; right_depth++; } if (left_depth == right_depth) return (2 << left_depth) - 1; return countNodes(root->left) + countNodes(root->right) + 1; } }; 广搜队列这个方法完全没有利用题面完全二叉树的特点，是一种通用的求二叉树节点数的方法。class Solution { public: int countNodes(TreeNode* root) { int result = 0; if (root == nullptr) return result; queue<TreeNode*> que; que.push(root); while (!que.empty()) { int size = que.size(); while (size--) { TreeNode* node = que.front(); que.pop(); result++; if (node->left) que.push(node->left); if (node->right) que.push(node->right); } } return result; } };

## Publication Information

- [Monkey船长](https://paragraph.com/@monkey-9/): Publication homepage
- [All Posts](https://paragraph.com/@monkey-9/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@monkey-9): Subscribe to updates