1008. 前序遍历构造二叉搜索树

左手的ㄟ右手 2022-12-22 08:52 105阅读 0赞

# 题目来源 #

[1008. 前序遍历构造二叉搜索树][1008.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
    public TreeNode bstFromPreorder(int[] preorder) {
        
            TreeNode root = null;
            for (int i = 0; i < preorder.length; i++){
        
                root = helper(root, preorder[i]);
            }
            return root;
        }
        
        private TreeNode helper(TreeNode root, int val){
        
            if (root == null){
        
                return new TreeNode(val);
            }
            
            if (root.val > val){
        
                root.left = helper(root.left, val);
            }else{
        
                root.right = helper(root.right, val);
            }
            
            return root;
        }
    }

![在这里插入图片描述][20201118202315884.png_pic_center]

[1008.]: https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/9ad25724826540c5b2b40fdee09cf56d.png
[20201118202315884.png_pic_center]: /images/20221120/10224319e0204d7cbe84af2d1eb5ab31.png