99클럽 코테 스터디 18일차 TIL - 트리 순회

문제

[Increasing Order Search Tree
]

풀이

• 이진 탐색 트리를 편향 이진 탐색 트리로 바꾸는 것
• 중위 순회로 val을 queue에 저장
• queue를 순회하면서 right에 node를 재생성

코드

class Solution {
    Queue<Integer> nodes = new LinkedList<>();
    
    public TreeNode increasingBST(TreeNode root) {
        if(root == null) return root;
        recur(root);
        
        TreeNode answer = new TreeNode(0, null, null);
        TreeNode temp = answer;
        
        while(!nodes.isEmpty()) {
            temp.right = new TreeNode(nodes.poll(), null, null);
            temp = temp.right;
        }
        
        return answer.right;
    }
    
    public void recur(TreeNode root){
        if(root == null) return;        
        recur(root.left);
        nodes.add(root.val);
        recur(root.right);

    }
}

정리

• 중위 순회를 먼저 하는 거는 금방 알았는데, 트리를 재구성하는 거 생각하는데 시간이 오래 걸림
• queue에서 하나씩 꺼내서 트리 만들고 right에 붙여야 하는데 그거 생각하는 게 어려웠음. temp 만들고 right에 노드 붙이고 다시 temp = temp.right를 해야함