###### tags: `Leetcode` `easy` `tree` `dfs` `python` `c++`

# 897. Increasing Order Search Tree

## [題目連結:] https://leetcode.com/problems/increasing-order-search-tree/description/

## 題目:
Given the ```root``` of a binary search 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 one right child.


## 解題想法:
* 此題為: 將此二元樹依照inorder重組為，左點為根結點，整棵樹不能有左節點

* 遞迴求解即可

## Python Sol1:
* time、space: O(n)
* 先inorder存於list 再重建tree

class Solution(object):
    def increasingBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.stack=[]
        self.dfs(root)
        newRoot=TreeNode(self.stack[0])
        tmp=newRoot
        for node in self.stack[1:]:
            tmp.right=TreeNode(node)
            tmp=tmp.right
        return newRoot
    
    def dfs(self,root):
        if not root:
            return 
        self.dfs(root.left)
        self.stack.append(root.val)
        self.dfs(root.right)

## Python Sol2:
* time: O(n) 、space: O(1)
* self.pre紀錄前一個節點，每次重建時處理當前root與self.pre之關係即可

class Solution(object):
    def increasingBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        dummy = TreeNode(0)
        self.pre=dummy #須隨時更新
        self.inorder(root)
        return dummy.right
    def inorder(self,root):
        if not root:
            return
        #遞迴左
        self.inorder(root.left)
        #處理當前
        curRoot=TreeNode(root.val)
        self.pre.right=curRoot
        self.pre=self.pre.right
        #遞迴右
        self.inorder(root.right)

## C++:

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode* dummy= new TreeNode(-1);
        pre=dummy;
        inorder(root);
        return dummy->right;
    }

    void inorder(TreeNode* root){
        if (root==nullptr)
            return;
        inorder(root->left);
        TreeNode* curRoot= new TreeNode(root->val);
        pre->left=nullptr;
        pre->right=curRoot;
        pre=pre->right;
        inorder(root->right);
    }
private:
    TreeNode *pre;
};