105. 从前序与中序遍历序列构造二叉树
方法一：
代码语言：javascript
复制/**
* 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[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
if (!preorder.length) return null;
const rootVal = preorder.shift(); // 从前序遍历的数组中获取中间节点的值， 即数组第一个值
const index = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
const root = new TreeNode(rootVal); // 创建中间节点
root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index)); // 创建左节点
root.right = buildTree(preorder.slice(index), inorder.slice(index 1)); // 创建右节点
return root;
};
106. 从中序与后序遍历中序列构造二叉树
方法一：
代码语言：javascript
复制/**
* 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) return null;
const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值， 即数组最后一个值
let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
const root = new TreeNode(rootVal); // 创建中间节点
root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 创建左节点
root.right = buildTree(inorder.slice(rootIndex 1), postorder.slice(rootIndex)); // 创建右节点
return root;
};
