[binary tree] preorder traversal to construct binary search tree

0x00 subject

Given a Integers Array
It said BST( The binary search tree ) Of The first sequence traversal
Construct the tree and return its The root node

---

0x01 Ideas

Of binary search trees Before the order Traverse
The first element is root node
Subsequent elements
Small At the root node is Left Elements of the subtree
Big At the root node is Right Elements of the subtree

---

0x02 solution

Language ：Swift

Tree node ：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

solution ：

func bstFromPreorder(_ preorder: [Int]) -> TreeNode? {
    if preorder.isEmpty { return nil }
    
    func build(_ start: Int, _ end: Int) -> TreeNode? {
        if start > end { return nil }
        else if start == end { return TreeNode(preorder[start]) }
        
        var l = start
        var r = end
        let first = preorder[start]
        
        //  In the interval  [l...r]  Internal search   the last one   Less than  first  The subscript 
        while l < r {
            let mid = l + (r - l + 1) / 2
            //  Look right 
            if preorder[mid] < first {
                l = mid
            }else{
                r = mid - 1
            }
        }
        
        //  The first element is the root node 
        let node = TreeNode(first)
        node.left = build(start+1, l)
        node.right = build(l+1, end)
        return node
    }
    
    let r = build(0, preorder.count-1)
    return r
}

---

0x03 My work

Welcome to experience one of my works ： Little notes -XNote
Take notes one step at a time
App Store Search ~

---