【4.25】LeetCode每日一题· 递增顺序搜索树

2021年04月25日 9时50分

标签： LeetCode dfs 树形结构

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

#### 示例1  
![](https://assets.leetcode.com/uploads/2020/11/17/ex1.jpg)
```
输入：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
![](https://assets.leetcode.com/uploads/2020/11/17/ex2.jpg)
```
输入：root = [5,1,7]
输出：[1,null,5,null,7]
```

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

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/increasing-order-search-tree%0A "题目链接")

## 解题思路
简单题，中序遍历二叉搜索树，并维护其**前驱节点**。每当遍历到一个节点时，将其连接到前驱节点的右孩子上，并将左孩子置为空。

需要特别注意的一点是，中序遍历完成后，二叉搜索树中最右边的节点的左孩子可能还未被置为`nullptr`，因此输出答案会产生错误（产生回环导致爆栈）。所以要手动将其置为`nullptr`。

## 代码
```cpp
/**
 * 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* pre;
    void dfs(TreeNode* root){
        if(root->left) dfs(root->left);
        pre->right = root;
        pre->left = nullptr;
        pre = root;
        if(root->right) dfs(root->right);
    }
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode* newRoot = new TreeNode();
        pre = newRoot;
        dfs(root);
        pre->left = nullptr; // 注意要把生成的顺序搜索树的最右边的节点的左子树置为空！！
        root = newRoot->right;
        delete newRoot;
        return root;
    }
};
```

### 用时和内存
> 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户
> 内存消耗：7.4 MB，在所有 C++提交中击败了77.43%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.25】LeetCode每日一题· 递增顺序搜索树

所有评论

暂无评论

新增评论