LeetCode 1008 Construct Binary Search Tree from Preorder Traversal

一份执着✘

发布于 2019-12-30 16:56:29

4980

发布于 2019-12-30 16:56:29

文章被收录于专栏：赵俊的Java专栏

题意

给定一个前序遍历的数组，还原 二叉搜索树。

数组中不存在重复值

例 :

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

解法

/**
 * 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) {
        if (preorder.length == 0) {
            return null;
        }
 
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);

        for (int i = 1; i < preorder.length; i++) {
            TreeNode temp = stack.peek();
            int n = preorder[i];
            if (n < temp.val) {
                temp.left = new TreeNode(n);
                stack.push(temp.left);
            } else {
                TreeNode prev = stack.pop();
                while (!stack.isEmpty() && stack.peek().val < n) {
                    prev = stack.pop();
                }
                prev.right = new TreeNode(n);
                stack.push(prev.right);
            }
        }
        return root;
    }
}

时间复杂度 O(n)，空间复杂度 O(n)。 Runtime: 1 ms, faster than 82.12% of Java online submissions for Construct Binary Search Tree from Preorder Traversal. Memory Usage: 36.8 MB, less than 100.00% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-03-27，如有侵权请联系 cloudcommunity@tencent.com 删除

java