이진 트리를 탐색하면서 오름차순으로 되어 있는 트리를 만들어서 return하는 문제이다.
중위순회를 통해 오름차순된 node들을 얻을 수 있다.
import java.util.*;
class Solution {
public TreeNode increasingBST(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
TreeNode answer = null;
TreeNode cur = null;
s.add(root);
while(!s.isEmpty()) {
TreeNode temp = s.pop();
if(temp.left != null) {
TreeNode next = temp.left;
temp.left = null;
s.add(temp);
s.add(next);
continue;
}
if(answer == null) {
answer = new TreeNode(temp.val);
cur = answer;
}
else {
cur.right = new TreeNode(temp.val);
cur = cur.right;
}
if(temp.right != null) {
TreeNode next = temp.right;
temp.right = null;
s.add(next);
}
}
return answer;
}
}