Leetcode - Construct Binary Tree from Preorder and Inorder Traversal

Leetcode - Construct Binary Tree from Inorder and Postorder Traversal

violet posted @ Apr 21, 2020 08:06:14 AM in 算法 with tags Algorithm Golang tree , 232 阅读

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

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

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

For example, given

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

Return the following binary tree:

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

func build(inorder, postorder []int, inStart, inEnd, postStart, postEnd int, hash map[int]int) *TreeNode {
    if inStart > inEnd || postStart > postEnd {
        return nil
    }
    root := &TreeNode{Val: postorder[postEnd]}
    index := hash[root.Val]
    root.Left = build(inorder, postorder, inStart, index-1, postStart, postStart + index - inStart - 1, hash)
    root.Right = build(inorder, postorder, index + 1, inEnd, postStart + index - inStart, postEnd - 1, hash)
    
    return root
}