leetcode_day20

今日内容

● 654.最大二叉树
● 617.合并二叉树
● 700.二叉搜索树中的搜索
● 98.验证二叉搜索树

最大二叉树

一般写法

题目实际上已经给出了递归逻辑，翻译成代码即可

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

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

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

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size() == 0) return nullptr;
        int max = 0;
        for(int i = 0;i < nums.size();i++) 
            if(nums[max] < nums[i]) max = i;
        TreeNode * root = new TreeNode(nums[max]);// 1创建一个根节点，其值为`nums`中的最大值。
        vector<int> left(nums.begin(), nums.begin() + max);
        vector<int> right(nums.begin() + max + 1, nums.end());
        root->left = constructMaximumBinaryTree(left);// 2递归地在最大值`左边`的`子数组前缀上`构建左子树。
        root->right = constructMaximumBinaryTree(right);// 3递归地在最大值`右边`的`子数组后缀上`构建右子树。
        return root;// 返回最大二叉树
    }
};

单调栈写法

笔者仅根据题目写出递归写法，未想到单调栈写法，此为力扣官方题解启发

总体思想图示

因此，我们的任务变为：找出每一个元素左侧和右侧第一个比它大的元素所在的位置。这就是一个经典的单调栈问题了，可以参考 503. 下一个更大元素 II。如果左侧的元素较小，那么该元素就是左侧元素的右子节点；如果右侧的元素较小，那么该元素就是右侧元素的左子节点。

class Solution {  //单调栈
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        int len = nums.size();
        if(len == 0){
            return nullptr;
        }
        vector<int> left(len, -1);  //每个节点左侧第一个更大的节点
        vector<int> right(len, -1);  //每个节点右侧第一个更大的节点
        stack<int> stk;
        vector<TreeNode*> tree(len);  //存储树节点
        //使用单减栈 获取left和right  (题目限制元素是不同的)
        for(int i = 0; i < len; i++){
            tree[i] = new TreeNode(nums[i]); //构造当前节点
            while(!stk.empty() && nums[i] > nums[stk.top()]){  //当前节点比栈中元素大 弹栈并给栈中的小元素赋right
                right[stk.top()] = i;
                stk.pop();
            }
            if(!stk.empty()){  //当前节点的左侧更大节点就是单减栈的顶部元素
                left[i] = stk.top();
            }
            stk.push(i);
        }
        TreeNode* root = nullptr;
        //将每个节点接到自己的父节点上以构造树形结构
        for(int i = 0; i < len; i++){
            if(left[i] == -1 && right[i] == -1){  //当前节点为最大值，其为根
                root = tree[i];
            }else if(left[i] == -1 || (right[i] != -1 && nums[left[i]] > nums[right[i]])){ 
                tree[right[i]]->left = tree[i];   //左侧没有更大的节点或左侧更大值大于右侧更大值，说明当前节点是右侧更大值的左子树的根节点
            }else{
                tree[left[i]]->right = tree[i];
            }
        }
        return root;
    }
};

该代码中的注释来源于题解评论区@健，本菜比瞪眼看了十分钟没看懂，抄了，挖坑后面来看

合并二叉树

简单递归即可

1. 确定返回值和参数：就按力扣给的核心函数递归就行，无需另写函数，返回值就是合并后的节点指针，参数就是要合并的两个节点
2. 确定递归结束条件：如果一方为空则返回另一方，都不空则相加后返回和节点
3. 确定递归中途操作：合并当前节点对应的左右孩子

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1) return root2;
        if(!root2) return root1;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

二叉搜索树中的搜索

过于简单，知道什么是二叉搜索树就能做，略

验证二叉搜索树

示例2就已经给出一个容易犯的陷阱：错误地以为只需要左右节点各比根节点小和大就可以了，实际上二叉搜索树需要整个左右子树都比根节点小和大，所以需要注意在想当然递归的时候不要只比较左右节点，还需注意更上层的节点。

由于是二叉搜索树，条件比较硬，所以可以充分利用二叉搜索树的特性————利用中序遍历获取序列，然后判断该序列是否单调递增就好，若不单调递增，证明不是二叉搜索树

二叉排序树左子树-根-右子树严格单调递增，标准地画出一棵二叉排序树，并从上到下作其投影可得到严格序列，该序列即是中序遍历序列，并且该序列单调递增

附图直观一览

二叉排序树的投影与中序遍历

class Solution {
public:
    vector<long long> ans;
    void traversal(TreeNode * root) {
        if(root) {
            traversal(root->left);
            ans.push_back(root->val);
            traversal(root->right);
        }
    }
    bool isValidBST(TreeNode* root) {
        traversal(root);
        vector<long long> ans2 = ans;
        sort(ans2.begin(), ans2.end());
        for(int i = 0;i < ans.size();i++) {
            if(ans[i] != ans2[i]) return false;
            if(i > 0 && ans2[i] <= ans2[i - 1]) return false;
        }
        return true;
    }
};