LeetCode-897-递增顺序搜索树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode-897-递增顺序搜索树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1583字，纯文字阅读大概需要3分钟。

内容图文

LeetCode-897-递增顺序搜索树

题目

给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例 1：

输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

提示：

树中节点数的取值范围是 [1, 100]
0 <= Node.val <= 1000

思路

如果按照题意，直接中序遍历构造一个新的二叉树，思路上相对简单，但是时间和空间复杂度较高

因此可以在中序遍历二叉树时，改变此二叉树的形状，使其符合题意。

根据观察，需求的二叉树左子树为空，右子树大于根节点，而BST的特点是左子树小于根节点，右子树大于根节点

因此可以将BST中每个节点的左子树变为父节点，然后左子树置为空即可，代码如下所示。

最后的结果时间0ms，空间6M。感觉只用了两个指针变量，不知道为啥会消耗这么多空间，可能算上了二叉树的大小。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* increasingBST(struct TreeNode* root){
    if (!root) return NULL;
    struct TreeNode* leftRootNode = root;
    if (root->left) {
        // 将左子树变成父节点
        leftRootNode = increasingBST(root->left);
        struct TreeNode* leftRightNode = root->left;
        while (leftRightNode->right) leftRightNode = leftRightNode->right;
        //printf("%d %d\n", leftRightNode->val, node->val);
        leftRightNode->right = root;
        root->left = NULL;
    }
    if (root->right) {
        // 改变右子树为右子树的返回值
        root->right = increasingBST(root->right);
    }
    // 若节点没有左子树，返回值为当前节点，若有，返回值为左子树的根节点
    return leftRootNode;
}

内容总结

以上是互联网集市为您收集整理的LeetCode-897-递增顺序搜索树全部内容，希望文章能够帮你解决LeetCode-897-递增顺序搜索树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---