一、题目
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。
二、示例
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
输入: preorder = [-1], inorder = [-1]
输出: [-1]
三、解题思路
本题给我们前序遍历和中序遍历,这样我们就可以确定一个树。本题中我们使用的是递归算法。本题以preorder = [3,9,20,15,7]
和inorder = [9,3,15,20,7]
为例。从先序遍历中我们可以知道根节点是3
,然后我们在进行查找在中序遍历中3
的左边为根节点的左子树的中序遍历,3
的右边为根节点的右子树的中序遍历,然后再从preorder
中查找左子树的先序遍历和右子树的先序遍历。最终再次使用递归算法即可。
四、代码
/**
* 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) {
let firstOne = preorder[0]
let node = new TreeNode(firstOne)
let index = inorder.findIndex(value => value === firstOne)
let leftPreOrder = preorder.slice(1, index + 1)
let rightPreOrder = preorder.slice(index + 1)
let leftInOrder = inorder.slice(0, index)
let rightInOrder = inorder.slice(index + 1)
if(leftInOrder.length && leftPreOrder) {
node.left = buildTree(leftPreOrder, leftInOrder)
}
if(rightInOrder.length && rightPreOrder.length) {
node.right = buildTree(rightPreOrder, rightInOrder)
}
return node
};
五、总结
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_47450807/article/details/123386424
内容来源于网络,如有侵权,请联系作者删除!