[leetcode #1008] Construct Binary Search Tree from Preorder Traversal

Problem

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.
It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.
A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.
A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.
Example 1:

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

Example 2:

Input: preorder = [1,3]
Output: [1,null,3]

Constraints:

・ 1 <= preorder.length <= 100
・ 1 <= preorder[i] <= 10⁸
・ All the values of preorder are unique.

Idea

これは、Preorderで表されるバイナリ検索ツリーのみを使用してツリーを再構築する問題です.Preorderは親ノードから始め、左、右の子ノードの順に値を入力します.また、作成するツリーはBST(binary search tree)であるため、preorder配列を順番に参照する場合は、親ノードの値を使用して、左側に入るサブノードと右側に入るサブノードを区別する必要があります.境界は順次検索できますが、O(n)が必要ですので、binary searchでO(nlogn)を検索するのが望ましいです.
Binary Searchで中間インデックスを求めます.インデックスが終了値、または親ノードの値が中間インデックス値と(中間インデックス+1)値の間に存在する場合、boundrayが見つかります.boundrayが見つからない場合は、境界が見つかるまで中間インデックスを開始インデックスまたは終了インデックスに置き換えます.
Binary Search関数を実装すると、BSTを作成できます.boundrayが見つかった場合、親ノードの左側は親ノードインデックスの次の境界、右側はboundray+1から終了インデックスであり、パラメータ呼び出し再帰関数として使用されます.すべてのサブノードが作成されている場合は、親ノードに戻ることができます.
Binary Searchの実現は雑すぎて、もっと簡潔な方法を探さなければなりません.いずれにしても、一度で解決できて満足!

Solution

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
    	return constructBst(preorder, 0, preorder.length-1);
    }

    private TreeNode constructBst(int[] preorder, int startIndex, int endIndex) {
        if (startIndex > endIndex)
            return null;

        TreeNode root = new TreeNode(preorder[startIndex]);
   
        int boundary = binarySearch(preorder, root.val, startIndex+1, endIndex);
   
        root.left = constructBst(preorder, startIndex+1, boundary);
        root.right = constructBst(preorder, boundary+1, endIndex);

        return root;
    }

    private int binarySearch(int[] preorder, int value, int startIndex, int endIndex) {
        int i = startIndex;
        int j = endIndex;
        int ret = 0;

        if (startIndex > endIndex)
            return endIndex;

        while (true) {
            int mid = i + (j - i)/2;
            if (mid == endIndex) {
                if (value > preorder[mid])
                    ret = mid;
                else
                    ret = mid-1;
                break;
            }
   
            if (value > preorder[mid] && value < preorder[mid+1]) {
                ret = mid;
                break;
            }
            else if (value < preorder[mid] && value < preorder[mid+1]) {
                if (mid == startIndex) {
                    ret = mid - 1;
                    break;
                }
                j = mid;
            }
            else if (value > preorder[mid] && value > preorder[mid+1]) {
                i = mid+1;
            }
        }
   
        return ret;
    }
}

Reference

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