Leetcode - Construct Binary Tree from Preorder and Inorder Traversal

violet posted @ Apr 21, 2020 07:47:37 AM in 算法 with tags Algorithm Golang tree , 274 阅读

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

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    hash := map[int]int{}
    for i, v := range inorder {
        hash[v] = i
    }
    return build(preorder, inorder, 0, len(preorder)-1, 0, len(inorder)-1, hash)
}

func build(preorder, inorder []int, preStart, preEnd, inStart, inEnd int, hash map[int]int)  *TreeNode {
    if preStart > preEnd || inStart > inEnd {
        return nil
    }
    root := &TreeNode{Val: preorder[preStart]}
    inRoot := hash[root.Val]
    numLeft := inRoot - inStart
    
    root.Left = build(preorder, inorder, preStart+1, preStart + numLeft, inStart, inRoot - 1, hash)
    root.Right = build(preorder, inorder, preStart + numLeft + 1, preEnd, inRoot + 1, inEnd, hash)
    
    return root
}