897 : Increasing Order Search Tree ( leetcode / java )

 

*해결 과정

 

모든 Tree를 순회하고, 오른쪽 트리만 계속 만들면 된다. 나는 ArrayList를 사용하고 get()을 통해 순회하였다. 여러가지 해설을 찾아보니 LinkedList로 선언하고 remove로 제거하면서 while에서 해결하는 것도 괜찮은 방법이라 생각한다.

 

 

*ArrayList 사용

import java.util.*;
class Solution {
    
    List<Integer> list = new ArrayList<>();
    
    public TreeNode increasingBST(TreeNode root) {
        DFS(root);
        Collections.sort(list);
        
        TreeNode node = new TreeNode(list.get(0));
        list.remove(0);
        makeTree(node, 0);
        return node;
    }
    
    public void makeTree(TreeNode root, int index){
        if(index==list.size()) return;
        TreeNode node = new TreeNode(list.get(index));
        root.right = node;
        makeTree(root.right,index+1);
    }
     
    public void DFS(TreeNode root){
        if(root==null) return;
        else list.add(root.val);
        
        if(root.left!=null) DFS(root.left);
        if(root.right!=null) DFS(root.right);
    }
}

 

 

*LinkedList 사용

class Solution {
    public TreeNode increasingBST(TreeNode root) {

        Queue<Integer> q = helper(root, new LinkedList<Integer>());
        TreeNode node = new TreeNode(q.remove());
        TreeNode res = node;
        while(!q.isEmpty()){
            int val = q.remove();
            node.right = new TreeNode(val);            
            node = node.right;
        }
        return res;
    }
    
    public LinkedList<Integer> helper(TreeNode root, LinkedList<Integer> ll){
        if(root == null){
            return null;
        }
        helper(root.left, ll);
        ll.add(root.val);
        helper(root.right, ll);
        return ll;
    }
}