🌵105. Construct Binary Tree from Preorder and Inorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
js
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
function buildTree(preorder, inorder) {
if (!preorder.length) {
return null
}
const root = new TreeNode(preorder[0])
const index = inorder.indexOf(preorder[0])
root.left = buildTree(preorder.slice(1, 1 + index), inorder.slice(0, index))
root.right = buildTree(preorder.slice(1 + index), inorder.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, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if not preorder:
return None
root = TreeNode(preorder[0])
index = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:1 + index], inorder[:index])
root.right = self.buildTree(preorder[1 + index:], inorder[index + 1:])
return rootgo
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
root := &TreeNode{Val: preorder[0]}
idx := 0
for i, val := range inorder {
if val == preorder[0] {
idx = i
break
}
}
root.Left = buildTree(preorder[1:1+idx], inorder[:idx])
root.Right = buildTree(preorder[1+idx:], inorder[idx+1:])
return root
}