输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
|
public class { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { TreeNode root = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1); return root; } private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
if(startPre>endPre||startIn>endIn) return null; TreeNode root = new TreeNode(pre[startPre]);
for(int i=startIn;i<=endIn;i++) if(in[i]==pre[startPre]){ root.left = reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1); root.right = reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn); break; }
return root; } }
|
近期评论