5
#yyds干货盘点# 面试必刷TOP101：重建二叉树
source link: https://blog.51cto.com/u_15488507/5645622
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 面试必刷TOP101：重建二叉树
精选 原创1.简述：
描述
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比
数据范围：，节点的值
要求：空间复杂度 ，时间复杂度
示例1
[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
{1,2,3,4,#,5,6,#,7,#,#,8}
返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示
示例2
[1],[1]
示例3
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
{1,2,5,3,4,6,7}
2.代码实现：
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return dfs(0, 0, in.length - 1, pre, in);
}
public TreeNode dfs(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
//创建结点
TreeNode root = new TreeNode(preorder[preStart]);
int index = 0;
//找到当前节点root在中序遍历中的位置，然后再把数组分两半
for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == root.val) { index = i; break; } } root.left = dfs(preStart + 1, inStart, index - 1, preorder, inorder); root.right = dfs(preStart + index - inStart + 1, index + 1, inEnd, preorder, inorder); return root;
}
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return dfs(0, 0, in.length - 1, pre, in);
}
public TreeNode dfs(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
//创建结点
TreeNode root = new TreeNode(preorder[preStart]);
int index = 0;
//找到当前节点root在中序遍历中的位置，然后再把数组分两半
for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == root.val) { index = i; break; } } root.left = dfs(preStart + 1, inStart, index - 1, preorder, inorder); root.right = dfs(preStart + index - inStart + 1, index + 1, inEnd, preorder, inorder); return root;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK