【二叉樹】前序周遊構造二叉搜尋樹

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

搜尋即可~