[LeetCode] 1008. Construct Binary Search Tree from Preorder Traversal

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

Construct Binary Search Tree from Preorder Traversal - LeetCode

 

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.)

Note: 

1. 1 <= preorder.length <= 100
2. The values of preorder are distinct.

해석

 

주어진 전위 순환(Preorder Traversal)과 매칭되는 이진탐색 트리의 루트 노드를 반환하라

(이진 탐색 트리는 모든 노드에 대하여 좌측의 자손이 value < node.val, 우측의 자손이 value > node.val인 이진 트리다. 또한 전위 순환은 노드의 값을 우선 표시한 다음, 좌측 노드 순환, 우측 노드를 순환 한다.)

Note:

1. 1 <= preorder.length <= 100
2. preorder의 값은 중복되지 않습니다.

 

기본지식

전위 순환(Preorder Traversal)

• 이진 트리를 순회하는 방법은 크게 4가지로 나뉜다
• 전위, 중위, 후위, 레벨
• 전위 순환은 노드의 값을 우선 방문한 후, 노드의 좌측을 전위 순환 , 노드의 우측을 전위 순환 한다.
• 위키백과 - 트리 순환[link] 글을 참고하고, 순회 방식에 따른 순회 순서가 아래 표시되어 있으니, 어떻게 다른지 꼭 확인해보자

 

 

예제 해석

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

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

Input을 주어진 조건에 맞게 이진 탐색 트리로 표시하면 위 그림과 같다.

 

솔루션 Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 int i = 0;
    public TreeNode bstFromPreorder(int[] A) {
        return preorderTravel(A, Integer.MAX_VALUE);
    }
    
    private TreeNode preorderTravel(int[] A, int bound){
        
        if(i >= A.length || A[i] > bound ) return null;
        
        TreeNode node = new TreeNode(A[i++]);
        
        node.left = preorderTravel(A,node.val);
        node.right = preorderTravel(A,bound);
        
        return node;
    }
    
}

 

입력으로 주어지는 배열 A는 이진탐색 트리를 전위 순환한 값이다.

이것을 활용하여 TreeNode를 생성할 때 전위 순환 방식으로 순환하며 해당 위치에 맞는 TreeNode를 생성한다.