【二叉樹】根據前序和後序周遊構造二叉樹

0x00 題目

給定兩個整數數組

​​

​preorder​

​​ 和 ​

​postorder​

​​ 其中 ​

​preorder​

​ 是一個具有 ​

​無重複​

​ 值的

二叉樹的​

​前序​

​周遊

​

​postorder​

​ 是同一棵樹的​

​後序​

​周遊

重構并傳回二叉樹

如果存在多個答案，您可以傳回其中 ​

​任何​

​ 一個

0x01 思路

二叉樹的周遊

​​

​前序​

​​周遊為：​

​中左右​

​​

​後序​

​周遊為：​

​左右中​

​

給定一棵二叉樹：​

​[1, 2, 3, 4, 5, 6, 7]​

​

前序周遊為：​

​[1]​

​​ + ​

​[2, 4, 5]​

​​ + ​

​[3, 6, 7]​

​​ 後序周遊為：​

​[4, 5, 2]​

​ + ​

​[6, 7, 3]​

​ + ​

​[1]​

​

左子樹

前序周遊時為：​​

​[2, 4, 5]​

​​ 後序周遊是為：​

​[4, 5, 2]​

​

順序剛好​

​相反​

​​ 在​

​後序周遊​

​中查找 ​

​2​

​，則可算出​

​索引​

​和​

​長度​

​ 進而區分出​

​左右子樹​

​

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 constructFromPrePost(_ preorder: [Int], _ postorder: [Int]) -> TreeNode? {
    // 為空 或 隻有一個元素時
    if preorder.isEmpty { return nil }
    if preorder.count == 1 { return TreeNode(preorder[0]) }
    
    func dfs(_ preStart: Int, _ postStart: Int, _ count: Int) -> TreeNode? {
        // 數量為 0 或 隻有一個元素時
        if count == 0 { return nil }
        if count == 1 { return TreeNode(preorder[preStart]) }
        
        // preStart 前序周遊數組的起點
        // postStart 後序周遊數組的起點        
        
        // length 為左子樹的長度
        var length = 1
        
        // 左子樹的第一個節點
        let p1 = preorder[preStart+1]
        
        // 從後序周遊數組中查找 p1
        for i in length..<count {
            let p2 = postorder[postStart+i-1]
            if p1 == p2 {
                length = i
                break
            }
        }
        
        // 前序周遊數組的起點 為根節點
        let root = TreeNode(preorder[preStart])
        // 建構左子樹
        root.left = dfs(preStart+1, postStart, length)
        // 建構右子樹
        root.right = dfs(preStart+length+1, postStart+length, count-length-1)
        // 結合這個來看，就比較清晰了
        // 前序周遊為：[1] + [2, 4, 5] + [3, 6, 7]
        // 後序周遊為：[4, 5, 2] + [6, 7, 3] + [1]
        return root
    }
    
    return dfs(0, 0, preorder.count)
}      

0x03 我的作品