Leetcode 1008) Construct Binary Search Tree from Preorder Traversal

30 Jun 2021 in Algorithms

내 답안

• stack 에 넣어서 계속 전것만 확인하려고 해서 잘 안 풀렸다.
• 새로운 숫자가 있으면 root부터확인해서 집어넣어줘야한다.

/**
 * 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 bstFromPreorder(int[] preorder){
        TreeNode root = new TreeNode(preorder[0]);
        int i=1;
        while(i < preorder.length){
            TreeNode dummy = root;
            while(dummy!=null){
                if(preorder[i] < dummy.val){
                    if(dummy.left==null){
                        dummy.left=new TreeNode(preorder[i]);
                        break;
                    }
                    dummy=dummy.left;
                }else{
                    if(dummy.right==null){
                        dummy.right = new TreeNode(preorder[i]);
                        break;
                    }
                    dummy=dummy.right;
                }
            }
            i++;
        }
        return root;
    }
}

다른 답안

/**
 * 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 {
    static int preIndex=0;
    public TreeNode bstFromPreorder(int[] preorder) {
        preIndex=0;
        return preorderBSTUtil(preorder,Integer.MIN_VALUE,Integer.MAX_VALUE,preorder[preIndex]);
    }
    public TreeNode preorderBSTUtil(int [] preorder,int min,int max,int key){
        // if(preIndex>=preorder.length){
        //     return null;
        // }
        TreeNode root=null; 
        if(key>min && key<max){
            root=new TreeNode(key);
            preIndex++;
            if(preIndex<preorder.length){
                root.left=preorderBSTUtil(preorder,min,key,preorder[preIndex]);
                
            }
             if(preIndex<preorder.length){
                root.right=preorderBSTUtil(preorder,key,max,preorder[preIndex]);
                
            }
        }
        return root;
    }
}