Pro 6 重建二叉树（java）

浏览数：26 / 时间：2015年06月08日

注：（1）java中树的构建

（2）构建子树时可以直接利用Arrays.copyOfRange(preorder, from, to),这个方法是左开右闭的

 1 package com.xsf.SordForOffer;
 2 
 3 import java.util.Arrays;
 4 
 5 /*剑指offer第6个问题
 6  根据前序和中序遍历来重建二叉树
 7  */
 8 class BinaryTreeNode {
 9     public int value;
10     public BinaryTreeNode leftNode;
11     public BinaryTreeNode rightNode;
12 }
13 
14 class ConstructCore {
15     /*
16      * 输入二叉树的前序遍历和中序遍历结果,重建二叉树并输出头节点 ex:12473568,47215386
17      */
18     public BinaryTreeNode constructCore(int[] preorder, int[] inorder)
19             throws Exception {
20         
21         if (preorder == null || inorder == null) {
22             return null;
23         }
24         if (preorder.length != inorder.length) {
25             throw new Exception("长度不一样－非法输入");
26         }
27         BinaryTreeNode root = new BinaryTreeNode();
28         for (int i = 0; i < inorder.length; i++) {
29             if (inorder[i] == preorder[0]) {
30                 // isHave = true;
31                 root.value = inorder[i];
32                 root.leftNode = constructCore(
33                         Arrays.copyOfRange(preorder, 1, i + 1),
34                         Arrays.copyOfRange(inorder, 0, i));
35                 root.rightNode = constructCore(
36                         Arrays.copyOfRange(preorder, i + 1, preorder.length),
37                         Arrays.copyOfRange(inorder, i + 1, inorder.length));
38             }
39         }
40         
41         return root;
42     }
43 
44     public void lastOrderTraverse(BinaryTreeNode T) {
45         if (T != null) {
46             lastOrderTraverse(T.leftNode);
47             lastOrderTraverse(T.rightNode);
48             System.out.print(T.value);
49         }
50     }
51 }
52 
53 public class Pro6Biconstruct {
54     public static void main(String[] args) throws Exception {
55         ConstructCore test = new ConstructCore();
56         int[] pre = { 1, 2, 4 };
57         int[] in = { 2, 1, 4 };
58         BinaryTreeNode root = test.constructCore(pre, in);
59         test.lastOrderTraverse(root);
60     }
61 }