Open Tcdian opened 4 years ago
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
var buildTree = function(inorder, postorder) {
if (inorder.length === 0) {
return null;
}
const val = postorder[postorder.length - 1];
const separator = inorder.indexOf(val);
const node = new TreeNode(val);
node.left = buildTree(inorder.slice(0, separator), postorder.slice(0, separator));
node.right = buildTree(inorder.slice(separator + 1), postorder.slice(separator, postorder.length - 1));
return node;
};
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
if (inorder.length === 0) {
return null;
}
const val = postorder[postorder.length - 1];
const separator = inorder.indexOf(val);
const node = new TreeNode(val);
node.left = buildTree(inorder.slice(0, separator), postorder.slice(0, separator));
node.right = buildTree(inorder.slice(separator + 1), postorder.slice(separator, postorder.length - 1));
return node;
};
106. Construct Binary Tree from Inorder and Postorder Traversal
根据一棵树的中序遍历与后序遍历构造二叉树。
Note
你可以假设树中没有重复的元素。
Example
For example, given
Return the following binary tree