代码随想录（二叉树所有题解）

前言

本文是基于代码随想录上二叉树章节的所有例题及其对应的算法思路（序号代表的是力扣题号）

算法思路主要参考（B站）：灵神 代码随想录 labuladong 懒猫老师 想象力少年 在此跪谢！！！

参考我的学习顺序：

• 1 懒猫老师的二叉树章节视频
• 2 labuladong二叉树纲领篇
• 3 刷题配合着灵神和官方讲解视频

labuladong二叉树纲领篇——遇到一道二叉树的题目时的通用思考过程是：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。
3、无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做。

226.翻转二叉树

算法思路及代码

solution 1 用分解问题的思路来解决

是我在没看题解之前自己想出来的方法
我是怎么想的呢：
我们既然需要翻转整颗二叉树那么我们不妨先翻转左子树，在翻转右子树，然后将跟节点的左右子树交换即可，这样就好啦
递归的结束条件就是节点为空时结束

solution 2 用遍历的思路来解决

这题我们只需要遍历一遍二叉树就可以解决问题，为什么这么说呢？
单独抽出来一个结点来 我们只需要交换左右结点 对不对？ 而且我们需要在往下去递归之前做这件事情，也就是在前序位置去交换左右节点 然后其余的结点交给递归就好

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution 1 {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==nullptr)
        {
            return nullptr;
        }
        TreeNode* right= invertTree(root->left);
        TreeNode* left= invertTree(root->right);
        root->right=right;
        root->left=left;
        return root;
    }
};
class Solution 2 {
public:
    // 主函数
    TreeNode* invertTree(TreeNode* root) {
        // 遍历二叉树，交换每个节点的子节点
        traverse(root);
        return root;
    }

    // 二叉树遍历函数
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }

        // *** 前序位置 ***
        // 每一个节点需要做的事就是交换它的左右子节点
        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;

        // 遍历框架，去遍历左右子树的节点
        traverse(root->left);
        traverse(root->right);
    }
};

101.对称二叉树

算法思路及代码

对于这题 我们先不管代码怎么实现，我们是不是同样遍历一遍二叉树就可以把这个问题解决掉 我们只需要每往下遍历以后 比较它的左右子树即可（后序位置上）

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

104.二叉树的最大深度

算法思路及代码

solution 1 遍历

对于这道题目我们首先是不是同样可以用遍历的思路来解决，终止条件就是到达叶子节点，我们只需要一个traverse函数和一个外部变量来实现就行，在刚刚进入一个结点的时候（前序位置）去更新我们的maxdepth，在离开一个节点之前（后序位置）去维护depth。

class Solution {

public:
    int depth = 0;
    int res = 0;

    int maxDepth(TreeNode* root) {
        traverse(root);
        return res;
    }

    // 遍历二叉树
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }

        // 前序遍历位置
        depth++;
        // 遍历的过程中记录最大深度
        res = max(res, depth);
        traverse(root->left);
        traverse(root->right);
        // 后序遍历位置
        depth--;
    }
};

solution 2 分解问题

我们要求一颗二叉树的最大深度，我们只需要分别知道它的左右子树的最大深度即可，然后return 1（根节点）+max（leftmax，rightmax）就行了

class Solution2 {
    // 定义：输入一个节点，返回以该节点为根的二叉树的最大深度
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        // 根据左右子树的最大深度推出原二叉树的最大深度
        return 1 + max(leftMax, rightMax);
    }
};

111.二叉树的最小深度

算法思路及代码

solution 1

// 「遍历」的递归思路
class Solution {
private:
    int minDepthValue = INT_MAX;
    int currentDepth = 0;

    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }

        // 做选择：在进入节点时增加当前深度
        currentDepth++;

        // 如果当前节点是叶子节点，更新最小深度
        if (root->left == nullptr && root->right == nullptr) {
            minDepthValue = std::min(minDepthValue, currentDepth);
        }

        traverse(root->left);
        traverse(root->right);

        // 撤销选择：在离开节点时减少当前深度
        currentDepth--;
    }

public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        traverse(root);
        return minDepthValue;
    }
};

solution 2

我觉得有了上一题的铺垫首先应该是想到这种办法，思路也非常明确，就是想找到左右子树各自的最小深度然后再加上根节点 但是力扣给的示例没有全部通过，它给的示例是一颗斜树，准确的来说是条五个节点的链表，这种就是极端的情况，我们怎么去解决它呢？
根本问题就是要防止当左子树为空时直接return 0的情况发生（参照下面的预期结果），所以我们就需要在即将离开一个节点之前判断此时的左右子树是否为空（也就是leftmin/rightmin为0的情况）
例如 leftmin=0，那么我们就return 1+rightmin（参考根节点的情况）就行了
那为什么在求最大深度的时候不会出现这个问题呢？
给我的感觉： 是因为在求最大深度时，我们的出口是到叶子节点就行（一股脑的往下冲），不会面临着是否为空的问题，
而我们要求最小深度时其实更像是一个探险的人，需要一步一步地走，需要避开危险

deepseek：
最小深度中，当左子树为空时(root.left为None)，右子树的深度决定了当前节点的最小深度。同理处理右子树为空的情况。只有左右子树均存在时，才取较小值加1，确保路径有效。（关键）
最大深度直接取左右子树的最大值加1，无需特殊处理空子树，因为空子树的深度0不会影响非空子树的最大值结果

• 修改之后AC

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==nullptr)
          {
            return 0;
          }
        int rightmin=minDepth(root->right);
        int leftmin=minDepth(root->left);
        if(leftmin==0)
        {
            return rightmin+1;
        }
        if(rightmin==0)
        {
            return leftmin+1;
        }
        return 1+min(leftmin,rightmin);
    }
};

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

算法思路和代码

solution 1

读完这道题我就有思路了，就是把左右子树的分别有多少个节点给他算出来，然后相加不就行了吗 确实能AC，也很简单
但是这题特意说了是完全二叉树的节点 意味着我们其实是可以利用完全二叉树的特性来解决问题的，这才是这题高效率的关键，因此就有了solution2

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==nullptr)
        {
            return 0;
        }
        int left=countNodes(root->left);
        
        int right=countNodes(root->right);
        int result=left+right+1;
        return result;

    }
};

solution 2

假如你学习过懒猫老师的课程，你一定知道如果给你一个满二叉树的深度k，那么它的节点数就是（2的k次方）-1，而给你一个二叉树的层数x，那么这一层有2的（X-1）次幂 个节点

#include <cmath>

class Solution {
public:
    int countNodes(TreeNode* root) {
        TreeNode* l = root;
        TreeNode* r = root;
        // 记录左、右子树的高度
        int hl = 0, hr = 0;
        while (l != nullptr) {
            l = l->left;
            hl++;
        }
        while (r != nullptr) {
            r = r->right;
            hr++;
        }
        // 如果左右子树的高度相同，则是一棵满二叉树
        if (hl == hr) {
            return (int)pow(2, hl) - 1;
        }
        // 如果左右高度不同，则按照普通二叉树的逻辑计算
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};