LeetCode - 先序遍历构造二叉树

LeetCode第1008题，难度中等，题目序号都在各种500开外乱飘。

原题地址：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/

题目描述：

返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）

示例：

输入：[8,5,1,7,10,12]

输出：[8,5,10,1,7,null,12]

提示：

1. 1 <= preorder.length <= 100
2. 先序 preorder 中的值是不同的。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

由于是先序遍历，所以就没有使用递归的方式。

首先将遍历的第一个节点作为根节点（这里需要回顾确认下先序遍历的意义）。然后开始遍历之后的每一个节点，由于该树是二叉搜索树，所以每个节点，都去从根节点开始往下遍历，找到NULL节点，将该节点设置为当前遍历到的节点，退出当前的遍历循环，继续下一个节点的遍历。

直到所有的节点都遍历结束之后，其实效率不高，因为每遍历一个节点，都需要从根节点开始遍历一次数组，进行一次搜索查询。但是实在没想到什么更好的办法

中文官网题解：

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

个人题解：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 1; i < preorder.length; i++) {
            TreeNode node = root;
            while (true) {
                if (preorder[i] < node.val) {
                    if (node.left == null) {
                        node.left = new TreeNode(preorder[i]);
                        break;
                    } else {
                        node = node.left;
                    }
                } else {
                    if (node.right == null) {
                        node.right = new TreeNode(preorder[i]);
                        break;
                    } else {
                        node = node.right;
                    }
                }
            }
        }
        return root;
    }
}

‍结果：

可能是人太少，所以还是100%吧，感觉已经很多次100%了，但是都是简单级别的啊。