LeetCode: Increasing Order Search Tree

문제 풀이

이진 트리를 탐색하면서 오름차순으로 되어 있는 트리를 만들어서 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;
    }
}