# 力扣刷题 Day16 - 104.111.222

By [Monkey船长](https://paragraph.com/@monkey-9) · 2023-03-31

---

今天（3.31）依旧在补昨天的任务，实际上这几天都是这样的模式。  
二叉树部分开始后有点放弃了思考，读完题面就去看题解，意识到这样子下去只会把题目水过去而已。为什么要刷题？我希望通过这个过程可以去锻炼自己的思维，以后遇到题目可以知道如何思考，更进一步希望可以教给学生如何思考。这和今天在 [科技爱好者周刊（第 248 期）：不要夸大 ChatGPT - 阮一峰的网络日志](http://www.ruanyifeng.com/blog/2023/03/weekly-issue-248.html) 中看到的学习微积分的一段话带给我的思考一致。

> 你学习微积分，不是因为要在日常生活中使用，而是因为它让你的思维变得更强大。

今天三道题目，我改为了先自己尝试去思考和写代码，然后再去看题解。虽然三道题目我都只是用广搜队列着同一个方法一遍 AC，但每次 AC 的感觉依旧很爽。  
看题解视频提到的递归遍历的方法对我还是不够熟悉的存在。经过三道题目递归遍历的洗礼，似乎有点掌握到递归的思路是什么，之后的题目要限定自己——先尝试看看递归如何去写。

104\. 二叉树的最大深度
--------------

[104\. 二叉树的最大深度 - 力扣（Leetcode）](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)

### 问题分析

*   二叉树节点的深度
    
    *   指从根节点到该节点的最长简单路径边的条数或者节点数
        
*   二叉树节点的高度
    
    *   指从该节点到叶子节点的最长简单路径边的条数后者节点数  
        根节点的高度就是二叉树的最大深度，可以用后序遍历求根节点高度，也可用前序遍历直接求深度。通过前序遍历，逻辑是先求得左右节点高度，在二者较大值基础上加一即为根结点高度。
        

### 代码实现

#### 后序遍历求高度

    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）](https://leetcode.cn/problems/minimum-depth-of-binary-tree/)

### 问题分析

和上面的「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）](https://leetcode.cn/problems/count-complete-tree-nodes/description/)

### 问题分析

如果是一棵满二叉树，若深度为 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;
        }
    };

---

*Originally published on [Monkey船长](https://paragraph.com/@monkey-9/day16-104-111-222)*