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

层序遍历、回溯·、由两种遍历序列逆推二叉树

654.最大二叉树

思路：
理解题意，找到数组最大值，其左元素为左子树，其右元素为右子树
特殊情况：

代码实现

class Solution {
public:
    int findMax(const vector<int>& nums, int left, int right){
        if(left > right) -1;
        int maxNum = nums[left]; int maxIndex = left;

        for(int i = left; i <= right; i++){
            if(nums[i] > maxNum) {
                maxIndex = i;
                maxNum = nums[i];
            }
        }

        return maxIndex;
    }

    TreeNode* BinaryTree(const vector<int>& nums, int left, int right){
        if(left > right) return nullptr;

        int rootIndex = findMax(nums, left, right);
        if(rootIndex < 0) return nullptr;

        TreeNode* node = new TreeNode(nums[rootIndex]);

        node->left = BinaryTree(nums, left, rootIndex-1);
        node->right = BinaryTree(nums, rootIndex+1, right);

        return node;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.empty()) return nullptr;

        return BinaryTree(nums, 0, nums.size()-1);
    }
};

617.合并二叉树

思路：
分三种情况合并：
当前节点的左右节点均为空，则合并结果为空；
左右节点存在一个为空，则合并结果为另一个节点；
左右节点均步为空，则创建一个新节点，其值为左右节点之和
特殊情况：

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr && root2 == nullptr) return nullptr;

        if(root1 == nullptr) return root2;
        if(root2 == nullptr) return root1;

        root1->val += root2->val;
        
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        
        return root1;
    }
};

700.二叉搜索树中的搜索

思想：二叉搜索树的节点值比左节点大，比右节点小
所以当前节点值比目标值小，则向右子树遍历；比目标值大，则向左子树遍历；

代码实现

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == nullptr) return nullptr;

        if(root->val == val) return root;

        TreeNode* node;
        if(root->val > val){
            node = searchBST(root->left, val);
        }
        else{
            node = searchBST(root->right,val);
        }

        return node;
    }
};

98.验证二叉搜索树

思想：二叉搜索树的中序序列时严格递增序列
步骤：
分几步：
● 第一步：中序遍历得到中序序列
● 第二步：遍历中序序列，若为递增则不是二叉搜索树

代码实现

class Solution {
public:

    void inOrder(TreeNode* root, vector<int> &InorderVals){
        if(root == nullptr) return;

        inOrder(root->left, InorderVals);
        InorderVals.push_back(root->val);
        inOrder(root->right, InorderVals);
    }

    bool isValidBST(TreeNode* root) {
        if(root == nullptr) return true;
        vector<int> InorderVals;
        
        inOrder(root, InorderVals);

        for(int i = 0; i < InorderVals.size()-1; i++){
            if(InorderVals[i] >= InorderVals[i+1]) return false;
        }

        return true;
    }
};