二刷代码随想录算法训练营第二十天 |654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

时间：2024-03-12 09:55:05

目录

一、654. 最大二叉树

二、617. 合并二叉树

 三、700. 二叉搜索树中的搜索

 四、验证二叉搜索树

一、654. 最大二叉树

题目链接：力扣

文章讲解：代码随想录

视频讲解： 又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树

题目：

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

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

代码：

dfs：

/**
 * 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* creat_tree(vector<int>& nums, int begin, int end){
        if(begin > end) return NULL;
        int target = begin;
        for (int i = begin+1; i <= end; i++)
            if (nums[target] < nums[i]) target = i;
        TreeNode* root = new TreeNode(nums[target]);
        if (begin == end) return root;
        root->left = creat_tree(nums, begin, target-1);
        root->right = creat_tree(nums, target+1, end);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return creat_tree(nums, 0, nums.size()-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) {
        int size = nums.size();
        vector<TreeNode*> stack;
        for (int i = 0; i < size; i++) {
            TreeNode* node = new TreeNode(nums[i]);
            while (!stack.empty()) {
                TreeNode* topnode = stack.back();
                if (topnode->val > node->val){
                    stack.push_back(node);
                    topnode->right = node;
                    break;
                }
                else{
                    stack.pop_back();
                    node->left = topnode;
                }
            }
            if (stack.empty()) stack.push_back(node);
        }
        return stack[0];
    }
};

时间复杂度: O(n)                                        空间复杂度: O(n)

⏲：35:37

总结：1、递归法类似昨天的通过不同遍历构造其他遍历，都是通过索引来构造新的树。2、单调栈：将题目转换为寻找每个数的左右边界（比这个数大的左右数），然后使用单调栈，保持小进，大出。

二、617. 合并二叉树

题目链接：力扣

文章讲解：代码随想录

视频讲解：一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树

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

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

代码：

/**
 * 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) {
        if (root1 == NULL) return root2;
        if (root2 == NULL) return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

时间复杂度: O(n)                                        空间复杂度: O(n)

⏲：1:13

总结：同时操作两棵树。

 三、700. 二叉搜索树中的搜索

题目链接：力扣

文章讲解：代码随想录

视频讲解：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索

题目：给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

代码：

/**
 * 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){
            if (root->val == val) return root;
            root = val < root->val ? root->left : root->right;
        }
        return NULL;
    }
};

时间复杂度: O(n)                                        空间复杂度: O(1)

⏲：1:15

总结：  二叉搜索树是一个有序树   (1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3)它的左、右子树也分别为二叉搜索树（3）二叉搜索树->中序遍历搞定一切问题！！（4）二叉搜索树设置一个pre节点+中序相当于遍历一个有序链表了

            注意不要只简单的以为只是比较root与左右的大小，可能存在，在root右侧，但是比root->left小的数。

 四、验证二叉搜索树

题目链接：力扣

文章讲解：代码随想录

视频讲解：你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树

题目：给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

代码：

/**
 * 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 = NULL;
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        bool left = isValidBST(root->left);
        if (pre && pre->val >= root->val) return false;
        pre = root;
        bool right = isValidBST(root->right);
        return left && right;
    }*/
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stack;
        TreeNode* pre = NULL;
        while (!stack.empty() || root) {
            if (root){
                stack.push(root);
                root = root->left;
            }
            else{
                root = stack.top();
                stack.pop();
                if (pre && pre->val >= root->val) return false;
                pre = root;
                root = root->right;
            }
        }
        return true;
    }
};

时间复杂度: O(n)                                        空间复杂度: O(n)

⏲：2:49

总结：中序遍历下，输出的二叉搜索树节点的数值是有序序列。

相关文章