Leetcode[day20] - Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제도 재귀함수를 생각했다.

 - 재귀함수를 좀 사용하다 보니, 특정 조건에서 재귀함수가 그만 돌고, 그렇지 않을 경우에는 해당 메소드를 계속해서 재귀호출하는 것으로 생각하는게 편하다는 것을 알게 되었다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 어느 조건에서 재귀함수를 멈출것인가?

 

3. 내가 작성한 알고리즘

 

 

/**
 * 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 head = new TreeNode(preorder[0]);
        for(int i=1; i < preorder.length; i++){
            setTree(head, new TreeNode(preorder[i]));    
        }
        return head;
    }
    
    private void setTree(TreeNode head, TreeNode treeNode){
        if(head.left == null && head.val > treeNode.val){
            head.left= treeNode;
        }
        else if(head.right == null && head.val < treeNode.val){
            head.right = treeNode;
        }
        else if(head.val > treeNode.val){
            setTree(head.left, treeNode);
        }
        else if(head.val < treeNode.val){
            setTree(head.right, treeNode);
        }
    }
}

4. 내가 작성한 알고리즘 결과

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/530/week-3/3305/

Explore - LeetCode