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 <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder and postorder consist of unique values.
  • Each value of postorder also appears in inorder.
  • inorder is guaranteed to be the inorder traversal of the tree.
  • postorder is guaranteed to be the postorder traversal of the tree.

解題

Runtime: 0 ms, faster than 100%
Memory Usage: 4.1 MB, less than 63.44%
/**
* 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) == 1 {
return &TreeNode{ Val: inorder[0] }
}
​
if len(postorder) == 0 {
return nil
}
​
midV := postorder[len(postorder) - 1]
for i, n := range inorder {
if n == midV {
left := buildTree(inorder[:i], postorder[:i])
right := buildTree(inorder[i+1:], postorder[i:len(postorder) - 1])
return &TreeNode{ Val: midV, Left: left, Right: right}
}
}
​
return nil
}
​
​