【剑指offer】重建二叉树

• 👑专栏内容：力扣刷题
• ⛪个人主页：子夜的星的主页
• 💕座右铭：前路未远，步履不停

---

---

一、题目描述

1、题目

剑指offer：重建二叉树

给定节点数为 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.只需要返回根结点，系统会自动输出整颗树做答案对比
数据范围：$n<=2000$，节点的值$-1000<=val<=1000$
要求：时间复杂度$O(n)$，空间复杂度$O(n)$

2、示例

示例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]
返回值：{1}

示例3

输入：[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值：{1,2,5,3,4,6,7}

二、题目分析

1、递归

public class Solution {public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {int n = pre.length;int m = vin.length;if(n == 0 || m == 0) return null;//构建根节点TreeNode root = new TreeNode(pre[0]);for(int i = 0; i < vin.length; i++){//找到中序遍历中的前序第一个元素if(pre[0] == vin[i]){ //构建左子树root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i)); //构建右子树root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length));break;}}return root;}
}

2、栈

public class Solution {public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {int n = pre.length;int m = vin.length;//每个遍历都不能为0if(n == 0 || m == 0) return null;Stack<TreeNode> s = new Stack<TreeNode>();//首先建立前序第一个即根节点TreeNode root = new TreeNode(pre[0]); TreeNode cur = root;for(int i = 1, j = 0; i < n; i++){//要么旁边这个是它的左节点if(cur.val != vin[j]){ cur.left = new TreeNode(pre[i]);s.push(cur);//要么旁边这个是它的右节点，或者祖先的右节点cur = cur.left; }else{j++;//弹出到符合的祖先while(!s.isEmpty() && s.peek().val == vin[j]){cur = s.pop();j++;}//添加右节点cur.right = new TreeNode(pre[i]); cur = cur.right;}}return root;}
}