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

今天三道题目，我改为了先自己尝试去思考和写代码，然后再去看题解。虽然三道题目我都只是用广搜队列着同一个方法一遍 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;
    }
};