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

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

思路

采用递归的方式处理。

在当前递归处理中，找到目前下标范围$[left,right]$内的最大值的下标$maxIdx$，以该位置的值建立当前子树的头节点，然后递归地将$[left,maxIdx?1]$范围内的递归结果作为左子树，将$[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.合并二叉树

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

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