105. Construct Binary Tree from Preorder and Inorder Traversal

題目

題目大意

解題思路

Big O

• 時間複雜 : O(n) n個樹節點

• 空間複雜 : O(n) 遞迴調用的Stack空間是 O(h)，其中 h 是樹的高度。 在每個遞迴層級中，都創建了一個 TreeNode 對象，因此空間複雜度也是 O(n)，其中 n 是節點的數量。 h< n所以空間複雜為 O(n)

來源

• https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
• https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0105.Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal/main.go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 時間複雜 O(), 空間複雜 O()
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    result := &TreeNode{preorder[0], nil, nil}

    i := 0
    for ; i < len(inorder); i++ {
        if preorder[0] == inorder[i] {
            break
        }
    }
    result.Left = buildTree(preorder[1:i+1], inorder[:i])
    result.Right = buildTree(preorder[i+1:], inorder[i+1:])

    return result
}

Benchmark