代码随想录C++算法训练，二叉树(day17)

笔端风月.

1105人浏览 · 2025-04-01 18:13:53

笔端风月. · 2025-04-01 18:13:53 发布

最大二叉树

题目链接：654. 最大二叉树 - 力扣（LeetCode）

题目描述：

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

题解：

/**
 * 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 {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        //构建一个新的根节点
        //如果输入数组只有一个元素，则将其作为叶子节点返回值
        TreeNode* node = new TreeNode(0);
        if(nums.size() == 1){
            node->val = nums[0];
            return node;
        }
        //初始化最大值及其索引
        int maxValue = 0;
        int maxValueIndex = 0;
        //遍历寻找最大值以及最大值的位置
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > maxValue){
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        //将当前节点的值设置为最大值
        node->val = maxValue;

        //最大值所在的下标左区间,递归构建左子树
        //如果左边还有元素的情况下
        if(maxValueIndex > 0){
            vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
            //递归调用
            node->left = constructMaximumBinaryTree(newVec);
        }

        //最大值所在的下右区间,递归构建右子树
        //如果右边还有元素的情况下
        if(maxValueIndex < nums.size() - 1){
            vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
            //递归调用
            node->right = constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};

总结与思考：

此题需要我们理解题意中构建二叉树的顺序与规则是什么，随后按部就班构建要求的最大二叉树
构建二叉树一般采用前序遍历，优先构建中间节点，随后再递归构建左右节点。
递归要注意的三个要点：

递归函数的参数和返回值：参数传入的是存放元素的数组，返回的是该数组构建成二叉树后的头节点，返回类型为指向节点的指针类型
递归函数的结束条件：当我们遍历到叶子节点时，应该构建一个新节点，并把数组的数值赋予给这个节点，随后返回这个节点。表示这个数组大小为1的时候，构建了一个新的节点并返回
单层递归的逻辑：第一步：我们需要找到数组中的最大值和最大值对应的下标，最大值构建为根节点，下标用来下一步分割数组。第二步：最大值所在的下标左区间，构建左子树。第三步：最大值所在的下标右区间，构建右子树。

此代码有非常大的优化空间，我们可以根据数组下标在原数组上进行操作来进行分割和构建子树，详见：代码随想录

合并二叉树

题目链接：617. 合并二叉树 - 力扣（LeetCode）

题目描述：

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,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 {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        //如果合并后，root1为空，则合并之后的树为root2。root2为空时同理。
        if(root1 == nullptr) return root2;
        if(root2 == nullptr) return root1;
        //这里默认修改了root1的结构
        root1->val += root2->val;//中
        root1->left = mergeTrees(root1->left, root2->left);//左
        root1->right = mergeTrees(root1->right, root2->right);//右
        return root1;
    }
};

总结与思考：

此题依旧使用递归的方式来解决问题，使用前序遍历合并两个二叉树
递归三要素：

递归函数的参数和返回值：因为要合并两个二叉树，所以参数分别为两个二叉树的根节点，并且要返回合并后的二叉树，所以返回值为合并后二叉树的根节点，类型为TreeNode*
递归函数的结束条件：两个二叉树合并后，必有一个二叉树为空，若t1为空，则合并后的二叉树为t2，对于t2为空时，同理
递归函数的单层逻辑：根据题目要求，就是将两个二叉树对应位置的val值相加到一起，因此单层逻辑为简单的t1->val += t2->val。若以root1为基础修改它的结构，则对于他的左子树来说就是合并 t1左子树与t2左子树。对于它的右子树来说，就是合并t1右子树与t2的右子树

二叉搜索树中的搜索

题目链接：700. 二叉搜索树中的搜索 - 力扣（LeetCode）

题目描述：

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

题解一：递归法

/**
 * 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 {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        //确定递归的结束条件
        if(root == nullptr || root->val == val) return root;
        //根据二叉搜索树的性质，可以锁定搜索的范围是在左子树或右子树
        //若root->val > val，则搜索其左子树，若root->val < val，则搜索其右子树
        //根据题意要求，定义该子树的根节点
        TreeNode* result = nullptr;
        if(root->val > val) result = searchBST(root->left, val);
        if(root->val < val) result = searchBST(root->right, val);
        return result;
    }
};

题解二：迭代法

/**
 * 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 {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root != nullptr){
            if(root->val > val) root = root->left;
            else if(root->val < val) root = root->right;\
            else return root;
        }
        //处理没找到目标值的情况
        return nullptr;
    }
};

总结与思考：

题解一使用递归法，对于递归法来说，重点为三要素：

递归函数的参数与返回值：传入的参数为要搜索的二叉搜索树与要搜索的值，返回值为搜索数值所在的节点
递归函数的结束条件：若root为空或找到了目标val值，则结束递归
递归函数的单层递归逻辑：因为二叉搜索树的节点是有序的，所以我们可以有方向的去寻找，若当前节点的值大于val，则进入该节点的左子树去搜索，若当前节点的值小于val，则进入该节点的右子树去搜索

题解二使用迭代法，对于二叉搜索树来说，我们不需要进行回溯的处理。根据二叉搜索树的有序性，已经帮我们决定好了搜索的路线顺序了。因此代码逻辑十分简短简单，别忘了处理没找到目标值的情况时，要返回NULL；

验证二叉搜索树

题目链接：98. 验证二叉搜索树 - 力扣（LeetCode）

题目描述：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

题解一：递归法（不转化为数组）

/**
 * 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 {
public:
    //记录上一个节点
    TreeNode* pre = nullptr;
    bool isValidBST(TreeNode* root) {
        if(root == nullptr) return true;
        //递归左子树
        bool left = isValidBST(root->left);

        if(pre != nullptr && pre->val >= root->val) return false;
        pre = root;//记录前一个节点

        //递归右子树
        bool right = isValidBST(root->right);

        return left && right;
    }
};

题解二：迭代法

bool isValidBST(TreeNode* root) {
    stack<TreeNode*> st;      // 用来模拟递归的栈
    TreeNode* cur = root;     // 当前访问的节点
    TreeNode* pre = nullptr;  // 记录前一个节点（用于比较是否递增）

    while (cur != nullptr || !st.empty()) {
        // 1. 先一路向左，把所有左子节点压入栈
        if (cur != nullptr) {
            st.push(cur);
            cur = cur->left;  // 移动到左孩子
        } 
        // 2. 左子树处理完毕，弹出栈顶节点（当前子树的根）
        else {
            cur = st.top();   // 取出栈顶节点
            st.pop();

            // 检查是否严格递增
            if (pre != nullptr && cur->val <= pre->val) {
                return false;  // 不是BST
            }
            pre = cur;        // 更新前一个节点

            // 3. 转向右子树
            cur = cur->right; // 移动到右孩子
        }
    }
    return true;  // 遍历结束，是BST
}

总结与思考：

此题我们使用递归法来做题解，递归法有两种方向：

因为二叉搜索树特殊的性质，我们可以将整个二叉树转换为数组，随后判断二叉树是否单调递增，由判断结果来下结论该二叉树是否为二叉搜索树
我们也可以直接在递归遍历的过程中判断整个二叉树是否有序，就不需要再单独转化为数组这一步了

我们使用第二种思路方向，递归的三要素：

递归函数的参数和返回值：我们需要判断一个二叉树是否为二叉搜索树，因此传入root，判断结果为true或false，因此返回值为bool类型
递归函数的结束条件：如果树为空，则说明该树也是二叉搜索树
递归函数的单层递归逻辑：使用中序遍历，根据左，中，右的顺序来遍历递归二叉树，一直比较前一个节点pre->val的值与下一个节点root->val的结果，若前者大于等于后者，说明这个二叉树并没有严格按照BTS的规则。return false；