【LeetCode】HOT 100（15）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】HOT 100（15）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题单介绍：

精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。

题单介绍：

题目：98. 验证二叉搜索树 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

题目：114. 二叉树展开为链表 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

写在最后：

题目：98. 验证二叉搜索树 - 力扣（Leetcode）

【LeetCode】HOT 100（15）

题目的接口：

/**
 * 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 isValidBST(TreeNode* root) {

    }
};

解题思路：

这道题我用的是前序遍历来判断的二叉搜索树，

我个人觉得前序遍历比较简单，

主要的思路如下：

前序遍历整个树，记录上一个节点的值，

在走左子树的时候，当前节点的值要比上一个节点的值要小，

在走右子树的时候，当前节点的值要比上一个节点的值要大，

我们直接通过函数参数传递上一个节点的值就行，

另外，这道题我一开始提交的时候，暴int了，所以只好改成long了

代码如下：

代码：

class Solution {
public:
    bool isValidBST(TreeNode* root, long left = LONG_MIN, long right = LONG_MAX) {
        if(root == nullptr) return true;
        long cur = root->val;
        return left < cur 
            && right > cur 
            && isValidBST(root->left, left, cur) //这里传的cur其实就是将上一个节点的值传下来
            && isValidBST(root->right, cur, right);
    }
};

过过过过啦！！！！

【LeetCode】HOT 100（15）

题目：114. 二叉树展开为链表 - 力扣（Leetcode）

【LeetCode】HOT 100（15）

题目的接口：

/**
 * 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:
    void flatten(TreeNode* root) {

    }
};

解题思路：

首先，进阶条件O（1）算法我做不到，

然后是这道题的思路，真的不知道他们是怎么想出来的，

我一开始的思路是先前序遍历一遍，把数值拿到手，存进数组，

然后用这个数组做一个链表，但是他需要原地转换，感觉不太行的通，就用了其他的方法。

具体思路如下：

把左子树嫁接到右子树，让原来的右子树嫁接到左子树的最右节点，

只到不存在左子树（全部根据题目要求置空）就能模拟出前序遍历，

如果有疑问可以画个图自己看一下，我这里就不演示了

代码如下：

代码：

/**
 * 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:
    void flatten(TreeNode* root) {
        while(root != nullptr) {
            if(root->left == nullptr) { //左子树为空
                root = root->right;
            }
            else { //存在左节点
                TreeNode* prev = root->left;
                while(prev->right) prev = prev->right; //找到左子树的最右节点 
                prev->right = root->right; //将原来的右子树移植到左子树的最右节点 
                root->right = root->left; //将左子树插入进右子树
                root->left = nullptr; //题目的要求，将左节点置空
                root = root->right; //继续找下一个左子树不为空的节点
            }
        }
    }
};