Leetcode

# 897. Increasing Order Search Tree

by hooni posted May 04, 2020
?

#### 단축키

Prev이전 문서

Next다음 문서

ESC닫기

크게 작게 위로 아래로 댓글로 가기 인쇄

Given 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 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  ```

Constraints:

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

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
TreeNode result;
TreeNode curr;

public TreeNode increasingBST(TreeNode root) {
makeFlatInOrder(root);

return result;
}

public void makeFlatInOrder(TreeNode node){
if(node == null){
return;
}

makeFlatInOrder(node.left);

if(curr == null){
result = new TreeNode(node.val);
curr = result;
}else{
curr.right = new TreeNode(node.val);
curr = curr.right;
}

makeFlatInOrder(node.right);
}
}```

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public TreeNode increasingBST(TreeNode root) {
List<TreeNode> list = new ArrayList<>();

inOrder(root, list);

TreeNode node = new TreeNode(-1);
TreeNode curr = node;

for(TreeNode item : list){
curr.right = new TreeNode(item.val);
curr = curr.right;
}

return node.right;
}

public void inOrder(TreeNode node, List<TreeNode> list){
if(node == null){
return;
}

inOrder(node.left, list);

inOrder(node.right, list);
}
}```

1 2 3 4