剑指Offer面试题:07 重建二叉树

时间:2021-6-19 作者:admin

算法不是金庸武侠小说里硬核的”九阳真经“,也不是轻量的”凌波微步“,它是程序员的基本功,如同练武之人需要扎马步一般。功夫好不好,看看马步扎不扎实;编程能力强不强,看看算法能力有没有。本系列采用leetcode题号,使用JavaScript为编程语言,每篇文章都会逐步分析解题思路,最终给出代码。文章一方面是记录笔者在刷题中的思路,已备学而时习之,另一方面也希望能跟大牛们多交流。有更高效的解法,或者文章有什么问题,都欢迎提出来,望诸位不吝赐教。

目录

一、题目:重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

剑指Offer面试题:07 重建二叉树

二、小马甲思路

其实这道题的关键在于了解前序、中序遍历是什么,了解它们的遍历特点,才能更进一步的分析。现在我们已知二叉树的前序遍历为[3,9,20,15,7],那能得出什么结论呢?对于前序遍历来说,根节点必是数组中第一个元素。
剑指Offer面试题:07 重建二叉树
已知二叉树的中序遍历为[9,3,15,20,7],由前序遍历知道3对应根节点,而对于中序遍历来说,根节点一定位于中间位置,即根节点左为左子树,根节点右为右子树。
剑指Offer面试题:07 重建二叉树
根据中序遍历的图我们再来看,整个数组代表一棵树,根节点的左边是一棵树,根节点右边也是一棵树,这就把大树分成了小树,对小树进行相同的拆分,直到只剩一个节点。每次处理一棵树,我们都生成一个根节点,并将其左右树递归进行处理,并赋给根节点的left和right属性。

总结一下有四步:

  1. 首先,根据前序遍历获取并生成根节点
  2. 其次,根据中序遍历获取中序左子树和中序右子树
  3. 再次,对左子树和右子树递归地执行1和2步骤,直到子树数量为1,则直接返回该节点
  4. 最后,将生成的子树添加至最初的根节点上

三、小马甲题解

我们知道前序遍历的第一个元素必对应根节点,因此直接生成一个根节点。

function TreeNode(key){
	this.key = key;
	this.left = this.right = null;
}

function buildTree(preorder, inorder){
	//if(preorder.length === 0){
	//	return null;
	//}
	//if(preorder.length === 1){
	//	return new Node(preorder[0]);
	//}

	let root = new TreeNode(preorder[0]);
}

我们已知根节点值,就能获取它在中序遍历数组中的位置inRootPos,根节点左边即中序左子树,根节点右边即为中序右子树,我们也能获取前序左子树,前序右子树。

function buildTree(preorder, inorder){
	//if(preorder.length === 0){
	//	return null;
	//}
	//if(preorder.length === 1){
	//	return new Node(preorder[0]);
	//}

	//let root = new TreeNode(preorder[0]);
	let inRootPos = inorder.indexOf(root);
	// 左子树前序序列
	let preorderLeft = preorder.slice(1, inRootPos + 1);
	// 左子树中序序列 
	let inorderLeft = inorder.slice(0, inRootPos);
	// 右子树前序序列 
	let preorderRight = preorder.slice(inRootPos + 1);
	// 右子树中序序列
	let inorderRight = inorder.slice(inRootPos + 1);
}

现在我们拥有了左右子树的前中遍历序列,可以递归地处理左右子树,并把它设置为根节点的左右子树。

function buildTree(preorder, inorder){
	//if(preorder.length === 0){
	//	return null;
	//}
	//if(preorder.length === 1){
	//	return new Node(preorder[0]);
	//}

	//let root = new TreeNode(preorder[0]);
	//let inRootPos = inorder.indexOf(root);
	// 左子树前序序列
	//let preorderLeft = preorder.slice(1, inRootPos + 1);
	// 左子树中序序列 
	//let inorderLeft = inorder.slice(0, inRootPos);
	// 右子树前序序列 
	//let preorderRight = preorder.slice(inRootPos + 1);
	// 右子树中序序列
	//let inorderRight = inorder.slice(inRootPos + 1);

	root.left = buildTree(preorderLeft, inorderLeft);
	root.right = buildTree(preorderRight, inorderRight);

	return root;
}

这个是我们的最终代码。

function TreeNode(key){
	this.key = key;
	this.left = this.right = null;
}

function buildTree(preorder, inorder){
	if(preorder.length === 0){
		return null;
	}
	if(preorder.length === 1){
		return new Node(preorder[0]);
	}

	let root = new TreeNode(preorder[0]);
	let inRootPos = inorder.indexOf(root);
	// 左子树前序序列
	let preorderLeft = preorder.slice(1, inRootPos + 1);
	// 左子树中序序列 
	let inorderLeft = inorder.slice(0, inRootPos);
	// 右子树前序序列 
	let preorderRight = preorder.slice(inRootPos + 1);
	// 右子树中序序列
	let inorderRight = inorder.slice(inRootPos + 1);

	root.left = buildTree(preorderLeft, inorderLeft);
	root.right = buildTree(preorderRight, inorderRight);

	return root;
}

四、总结

本文先从分析二叉树的前序遍历、中序遍历入手,给出了四步的解题思路。再将思路逐步用代码实现,把大问题拆小,递归地处理左右子树,最终得到了JavaScript版的算法程序。

基础知识关键字:二叉树、树的遍历、递归

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。