LeetCode Top Interview 150
106. Construct Binary Tree from Inorder and Postorder Traversal
Medium
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Constraints:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorderandpostorderconsist of unique values.- Each value of
postorderalso appears ininorder. inorderis guaranteed to be the inorder traversal of the tree.postorderis guaranteed to be the postorder traversal of the tree.
Solution
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
inIndex := []int{len(inorder) - 1}
postIndex := []int{len(postorder) - 1}
return helper(inorder, postorder, inIndex, postIndex, 1<<31-1)
}
func helper(in, post []int, index, pIndex []int, target int) *TreeNode {
if index[0] < 0 || in[index[0]] == target {
return nil
}
root := &TreeNode{Val: post[pIndex[0]]}
pIndex[0]--
root.Right = helper(in, post, index, pIndex, root.Val)
index[0]--
root.Left = helper(in, post, index, pIndex, target)
return root
}