周总结：2021-11-08——11-14

2023-12-27 22:37:15

周总结：2021-11-08——11-14

这里是这一周来刷题时印象比较深的几道题，挑出来做个总结

173. 二叉搜索树迭代器和剑指 Offer II 055. 二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

周总结：2021-11-08——11-14

输入
[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False

这是一道实现题，要我们实现三个函数的功能，要实现这个功能，我们的迭代器要做成一条单一的链，而不是树的情况（不然next和hasNext的遍历比较麻烦），首先我们要先准备一个成员变量的树节点p作为最开始的头指针，这个节点的值因为题目要求说比所给树的所有节点都小，那我们就找这个树最小的节点-1即可，先中序遍历一遍root，用所得到的中序序列来初始化p，每次从中序序列里取一个值初始化p的right节点，以此往复。最后就得到了一条只有right的树，且这个树的节点值递增的，也就是之前所给树的中序序列。一开始p是头结点，它的下一个才是根节点，然后next就把p往right走并返回节点值即可。hasNext即判断p->right是否为空，如果为空就返回false，不为空就返回true。

/**
 * 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 BSTIterator {
private:
    TreeNode* p;
public:
    BSTIterator(TreeNode* root) {
        vector<int>v;
        stack<TreeNode*>sta;
        while(sta.size()||root)
        {
            while(root)
            {
                sta.push(root);
                root=root->left;
            }
            root=sta.top();
            sta.pop();
            v.push_back(root->val);
            root=root->right;
        }
        this->p=new TreeNode(v[0]-1);
        dfs(p->right,v,0);
    }

    void dfs(TreeNode *&p,vector<int>v,int i)
    {
        if(i>=v.size())return;
        p=new TreeNode(v[i++]);
        dfs(p->right,v,i);
    }
    
    int next() {
        this->p=this->p->right;
        return this->p->val;
    }
    
    bool hasNext() {
        return (p->right)==NULL?false:true;
    }
};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

98. 验证二叉搜索树和面试题 04.05. 合法二叉搜索树

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

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

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

示例 1：

周总结：2021-11-08——11-14

输入：root = [2,1,3]
输出：true

咋一看，好像每次只当前节点值要小于右节点并且大于左节点就行，但不光是这样，它是整个左子树上的值都要小于当前节点，右子树上的值都要大于当前节点，比如如果上面的左节点1连了一个右节点5，虽然满足了1节点的条件，但根节点2要小于5，所以不满足左子树上所有值小于当前节点的设定了。

所以我们每次递归遍历的时候，要顺便传入一个最大值和最小值，一开始最大值最小值都是NULL，随着递归的进行，对于左子树来说：最小值会变成当前节点左子树的值，最大值会变成当前节点的值；对于右子树来说：最小值会变成当前节点的值，最大值会变成当前节点右子树的值。这样当每次遍历时，判断这个节点的val值是否在最小值和最大值之间，如果不在就说明不是一个合格的搜索二叉树。

/**
 * 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:
    bool flag=true;
    bool isValidBST(TreeNode* root) {
        if(!root->left&&!root->right)return flag;
        dfs(root,NULL,NULL);
        return flag;
    }
    void dfs(TreeNode* root,TreeNode* max,TreeNode* min)
    {
        if(!flag||!root)return;
        
        if(max&&root->val >= max->val)flag=false;
        if(min&&root->val <= min->val)flag=false;

        if(root->left)dfs(root->left,root,min);
        if(root->right)dfs(root->right,max,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:
    vector<int>v;
    bool isValidBST(TreeNode* root) {
        if(!root->left&&!root->right)return true;
        dfs(root);
        int n=v.size();
        for(int i=0;i<n-1;i++)
        {
            if(v[i]>=v[i+1])
                return false;
        }
        return true;
    }
    void dfs(TreeNode* root)
    {
        if(!root)return;
        dfs(root->left);
        v.push_back(root->val);
        dfs(root->right);
    }
};

538. 把二叉搜索树转换为累加树和1038. 把二叉搜索树转换为累加树和剑指 Offer II 054. 所有大于等于节点的值之和

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

周总结：2021-11-08——11-14

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

准备一个vector容器v，然后对root中序遍历，每遍历到一个节点时，先用这个节点的值对v中所有元素相加，然后再把这个节点的值插入v中，这样最好得到的是所有大于等于当前节点的和了，再遍历一遍root，把节点值用v中的值替换掉即可。

/**
 * 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:
    vector<int>v;
    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        int i=0;
        dfs2(root,i);
        return root;
    }
    void dfs(TreeNode* root)
    {
        if(!root)return;
        dfs(root->left);
        for(int& i:v)
            i+=root->val;
        v.push_back(root->val);
        dfs(root->right);
    }
    void dfs2(TreeNode*& root,int& i)
    {
        if(!root)return;
        dfs2(root->left,i);
        root->val=v[i++];
        dfs2(root->right,i);
    }
};

1008. 前序遍历构造二叉搜索树

返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。

(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，前序遍历首先显示节点 node 的值，然后遍历 node.left，接着遍历 node.right。）

题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。

示例：

输入：[8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

周总结：2021-11-08——11-14

因为是前序遍历，所以我们知道序列的第一个值为根节点，然后就像我们之前知道的，左子树的所有值小于根节点，右子树的所有值大于根节点，那么我们可以遍历一遍序列，把所有小于第一个值的元素存入一个vector容器v1里，大于第一个值的元素存入另一个vector容器v2里。再利用这两个数组分别去构造左右子树（重复如上步骤），最后得到的就是原来的二叉树了。

/**
 * 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* bstFromPreorder(vector<int>& preorder) {
        TreeNode* root;
        dfs(root,preorder);
        return root;
    }
    void dfs(TreeNode*&root,vector<int>preorder)
    {
        if(!preorder.size())return;
        vector<int>v1;
        vector<int>v2;
        int num=preorder[0],n=preorder.size();
        for(int i=1;i<n;i++)
            if(preorder[i]<num)
                v1.push_back(preorder[i]);
            else
                v2.push_back(preorder[i]);
        root=new TreeNode(num);
        dfs(root->left,v1);
        dfs(root->right,v2);
    }
};
上一篇：【Spring Boot 2.0学习之旅-08】SpringBoot数据库操作之整合Mybatis和事务讲解


下一篇：08 力扣热题刷题记录之第21题合并两个有序链表