力扣练习003---先序遍历构造二叉树(1008)

题目描述：

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、什么是二叉搜索树？对于所有子树来说，左子树所有节点的取值均小于根节点、右子树所有节点的取值均大于根节点

2、由于输入是先序遍历，因此构造二叉树也要按照先序来构造，即将第一个元素作为根节点，然后先构造左子树再构造右子树

3、对于二叉树相关题目，我的习惯数据结构是栈

解题思路：

1、第一个元素作为根节点，并且入栈；

2、遍历剩余元素，先构造左子树，也就是取值小于根节点取值的节点（根节点即为当前栈顶元素），将该节点作为根节点的左节点并将其入栈；

这样左子树中的左节点即被构造出来，接下来需要构造左子树中的右节点；

3、输入元素取值大于当前根节点取值，此时需要找到和该取值最为接近，并且取值小于该取值的节点；

方法是：执行出栈操作，直到栈空或者栈顶元素取值大于该节点取值，并且将该节点作为最近一次出栈节点的右节点；

并将该节点入栈(这里要入栈，因为该节点也可能存在左节点，我第一次就搞错了)

4、按照2/3两步，剩余元素遍历完成，二叉树也就构造好了

Java代码：

public class LeetCode1008_bstFromPreorder {
    
    public TreeNode bstFromPreorder(int[] preorder) {
        int lenght = preorder.length;
        if (lenght == 0) {
            return null;
        }
        
        TreeNode rootNode = new TreeNode(preorder[0]);
        Stack<TreeNode> stack = new Stack<>();
        stack.push(rootNode);
        for (int i = 1; i < lenght; i++) {
            TreeNode subNode = new TreeNode(preorder[i]);
            TreeNode stackTop = stack.peek();
            if (subNode.val < stackTop.val) {
                // 取值小于栈顶元素, 入栈，并作为栈顶元素的左节点
                stack.push(subNode);
                stackTop.left = subNode;
            } else {
                // 取值大于栈顶元素, 出栈, 直到栈空或者节点取值小于栈顶元素
                while (!stack.isEmpty() && !(subNode.val < stack.peek().val)) {
                    stackTop = stack.pop();
                }
                // 当前元素作为最后一个出栈的元素的右节点, 并入栈
                stackTop.right = subNode;
                stack.push(subNode);
            }
        }

        return rootNode;
    }
    
    class TreeNode {
        int val;

        TreeNode left;

        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}

力扣运行结果：