【二叉树】前序遍历构造二叉搜索树

0x00 题目

给定一个整数数组
它表示BST(即二叉搜索树 )的 先序遍历
构造树并返回其根节点

---

0x01 思路

二叉搜索树的前序遍历
第一个元素是根节点
往后的元素
小于根节点的是左子树的元素
大于根节点的是右子树的元素

---

0x02 解法

语言：Swift

树节点：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
    }
}

解法：

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]
        
        // 在区间 [l...r] 内找 最后一个 小于 first 的下标
        while l < r {
            let mid = l + (r - l + 1) / 2
            // 小于往右找
            if preorder[mid] < first {
                l = mid
            }else{
                r = mid - 1
            }
        }
        
        // 第一个元素是根节点
        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 我的作品

欢迎体验我的作品之一：小笔记-XNote
让笔记一步到位
App Store 搜索即可~

---