首页 > 代码库 > 重建二叉树
重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { return reConBTree(pre,0,pre.length-1,in,0,in.length-1); } public TreeNode reConBTree(int [] pre,int preleft,int preright,int [] in,int inleft,int inright){ if(preleft > preright || inleft> inright)//当到达边界条件时候返回null return null; //新建一个TreeNode TreeNode root = new TreeNode(pre[preleft]);//前序数组第一个元素就是根节点 //对中序数组进行输入边界的遍历 for(int i = inleft; i<= inright; i++){ if(pre[preleft] == in[i]){ //重构左子树，注意边界条件 root.left = reConBTree(pre,preleft+1,preleft+i-inleft,in,inleft,i-1); //重构右子树，注意边界条件 root.right = reConBTree(pre,preleft+i+1-inleft,preright,in,i+1,inright); } } return root; }}
重建二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。