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

2024-01-01 17:29:19

654.最大二叉树

题目链接:654.最大二叉树

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

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

返回 nums 构建的 最大二叉树

文章讲解/视频讲解:https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

采用递归的方式处理。

在当前递归处理中,找到目前下标范围 [ l e f t , r i g h t ] [left, right] [left,right]内的最大值的下标 m a x I d x maxIdx maxIdx,以该位置的值建立当前子树的头节点,然后递归地将 [ l e f t , m a x I d x ? 1 ] [left, maxIdx-1] [left,maxIdx?1]范围内的递归结果作为左子树,将 [ m a x I d x + 1 , r i g h t ] [maxIdx+1, right] [maxIdx+1,right]范围内的递归结果作为右子树。

C++实现

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return Traversal(nums, 0, nums.size() - 1);
    }

    TreeNode* Traversal(const vector<int>& nums, int left, int right){
        if(left > right) return nullptr;
        int maxIdx = left;
        for(int i = left;i<=right;i++){
            if(nums[i] > nums[maxIdx]){
                maxIdx = i;
            }
        }
        TreeNode* head = new TreeNode(nums[maxIdx]);
        head->left = Traversal(nums, left, maxIdx - 1);
        head->right = Traversal(nums, maxIdx + 1, right);
        return head;
    }
};

617.合并二叉树

题目链接:617.合并二叉树

给你两棵二叉树: root1root2

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

返回合并后的二叉树。

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

文章讲解/视频讲解:https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

利用递归来实现,让两棵树root1和root2同时前序遍历。

每次递归过程中,只有两棵树当前节点均为nullptr时才直接return,否则按照题目规则,如果两棵树当前节点均不为空,则将两个节点的值累加,利用累加值构建新树的节点,如果只有一棵树当前节点不为空,则用这个不为空的节点的值构建新树的节点。

C++实现

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr && root2 == nullptr) return nullptr;
        int cur_val;
        if(root1 != nullptr && root2 != nullptr){
            cur_val = root1->val + root2->val;
        }
        else if(root1 != nullptr && root2 == nullptr){
            cur_val = root1->val;
        }
        else{
            cur_val = root2->val;
        }
        TreeNode* cur = new TreeNode(cur_val);
        cur->left = mergeTrees(root1 == nullptr ? nullptr : root1->left, root2 == nullptr ? nullptr : root2->left);
        cur->right = mergeTrees(root1 == nullptr ? nullptr : root1->right, root2 == nullptr ? nullptr : root2->right);
        return cur;
    }
};

700.二叉搜索树中的搜索

题目链接:700.二叉搜索树中的搜索

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

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

文章讲解/视频讲解:https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html

思路

可采用最基本的递归查询。

因为root是一棵二叉搜索树,在每一次递归判断过程中,如果val等于当前子树的节点值,则直接返回该节点;如果val小于当前子树的节点值,则递归往当前子树的左子树寻找;如果val大于当前子树的节点值,则递归往当前子树的右子树寻找。如果最终没有找到,返回空指针。

C++实现

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root) return root;
        if(val == root->val) return root;
        else if(val < root->val) return searchBST(root->left, val);
        else return searchBST(root->right, val);
    }
};

98.验证二叉搜索树

题目链接:98.验证二叉搜索树

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

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

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

文章讲解/视频讲解:https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

思路

总体上用递归的方式来处理。

对于当前子树cur,如何判断cur是一棵二叉搜索树呢?cur比它左子树中所有的节点值大,比右子树中所有的节点值小;或者,cur是空节点或叶子节点。

那么如何找到cur左子树中值最大的节点?如果cur的左子树已经是二叉搜索树,那么cur左子树中值最大的节点是cur左子树中最右边的节点。

寻找cur右子树中值最小的节点同理,如果cur的右子树已经是二叉搜索树,那么cur右子树中值最大的节点是cur右子树中最左边的节点。

C++实现

class Solution {
public:
    int findRight(TreeNode* node){
        while(node->right) node = node->right;
        return node->val;
    }

    int findLeft(TreeNode* node){
        while(node->left) node = node->left;
        return node->val;
    }

    bool isValidBST(TreeNode* root) {
        if(!root || (!root->left && !root->right)) return true;
        bool left_success = isValidBST(root->left);
        bool right_success = isValidBST(root->right);

        if(!left_success || !right_success) return false;
        
        return (!root->left || root->val > findRight(root->left)) && (!root->right || root->val < findLeft(root->right));
    }
};

文章来源:https://blog.csdn.net/weixin_43347688/article/details/135326603
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。