🌵106. Construct Binary Tree from Inorder and Postorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
js
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
function buildTree(inorder, postorder) {
if (!postorder.length) {
return null
}
const root = new TreeNode(postorder[postorder.length - 1])
const index = inorder.indexOf(root.val)
root.left = buildTree(inorder.slice(0, index), postorder.slice(0, index))
root.right = buildTree(inorder.slice(index + 1), postorder.slice(index, -1))
return root
}py
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if not postorder:
return None
root = TreeNode(postorder[-1])
index = inorder.index(root.val)
root.left = self.buildTree(inorder[:index], postorder[:index])
root.right = self.buildTree(inorder[index + 1:], postorder[index:-1])
return rootgo
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
if len(postorder) == 0 {
return nil
}
root := &TreeNode{Val: postorder[len(postorder)-1]}
idx := 0
for i, val := range inorder {
if val == root.Val {
idx = i
break
}
}
root.Left = buildTree(inorder[0:idx], postorder[0:idx])
root.Right = buildTree(inorder[idx+1:], postorder[idx:len(postorder)-1])
return root
}