897. Increasing Order Search Tree

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child. ``` Example 1: Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

``````  5
/ \
3   6
``````

/ \
2 4 8
/ /
1 7 9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

1

2

3

4

5

6

7

8

9

``````Note:

1.  The number of nodes in the given tree will be between 1 and 100.
2.  Each node will have a unique integer value from 0 to 1000.

<br>

4
``````

/
2
/
1 3

``````当运行到结点3的时候，pre 应该带入的是结点4，这样就可以把结点4连到结点3的右下方，从而正确的捋直，参见代码如下：

<br>

``````

class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
return helper(root, nullptr);
}
TreeNode* helper(TreeNode* node, TreeNode* pre) {
if (!node) return pre;
TreeNode* res = helper(node->left, node);
node->left = nullptr;
node->right = helper(node->right, pre);
return res;
}
};

``````<br>

<br>

``````

class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
TreeNode *dummy = new TreeNode(-1), _pre = dummy;
stack st;
while (root || !st.empty()) {
while (root) {
st.push(root);
root = root->left;
}
root = st.top(); st.pop();
pre->right = root;
pre = pre->right;
root->left = nullptr;
root = root->right;
}
return dummy->right;
}
};

``````<br>
Github 同步地址:

<https://github.com/grandyang/leetcode/issues/897>

<br>

<https://leetcode.com/problems/increasing-order-search-tree/>

<https://leetcode.com/problems/increasing-order-search-tree/discuss/251290/C%2B%2B-short-iterative>

<https://leetcode.com/problems/increasing-order-search-tree/discuss/165885/C%2B%2BJavaPython-Self-Explained-5-line-O(N)>

<br>
[LeetCode All in One 题目讲解汇总(持续更新中...)](https://www.cnblogs.com/grandyang/p/4606334.html)
``````

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation