根据前序遍历和中序遍历结果重建二叉树
2015-07-10
次访问
package com.study;
/*
* 根据二叉树的前序遍历和中序遍历结果重建二叉树
* 并输出其头节点。假设前序遍历和中序遍历结果中没有重复数字
* 前序遍历序列：{1，2，4，7，3，5，6，8}
* 中序遍历序列：{4，7，2，1，5，3，8，6}
* **/
class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode() {
}
}
public class suanfa4 {
private static int[] arr1 = {1,2,4,7,3,5,6,8};
private static int[] arr2 = {4,7,2,1,5,3,8,6};
public static TreeNode RebuildBinaryTree() {
TreeNode head = null;
head = ConstructBTree( head ,arr1, 0, 7, arr2, 0, 7);
return head;
}
public static TreeNode ConstructBTree(TreeNode node, int[] pre, int pre_start, int pre_end,
int[] inorder, int inorder_start, int inorder_end) {
//System.out.println("pre_start:" + pre_start);
//System.out.println("pre_end: "+ pre_end);
/*if(pre_start > pre_end || pre_end > pre.length)
return null;*/
/*刚开始想着这里应该增加这样一个递归结束条件，但是在调试的过程中发现，如果增加了的话，则不能将最后
的叶子节点加到二叉树中，而且后面的判断左子树长度和右子树长度会自然结束递归*/
TreeNode root = new TreeNode();
root.data = pre[pre_start]; //找到根节点
root.left = root.right = null;
//System.out.println("root :"+ root.data);
int pos = FindPos(root.data, inorder); //在中序遍历的数组中找到根节点的位置
int Left_Length = pos - inorder_start;
int Right_Length = inorder_end - pos;
//System.out.println("左子树长度" + Left_Length);
//System.out.println("右子树长度" + Right_Length);
if( Left_Length > 0) { //存在左子树
TreeNode LeftRoot = new TreeNode();
LeftRoot.data = pre[pre_start + 1]; //左根节点
root.left = ConstructBTree(LeftRoot, pre , pre_start + 1, pre_start + Left_Length, inorder,
inorder_start , pos - 1);
}
if( Right_Length > 0) { //存在右子树
TreeNode RightRoot = new TreeNode();
RightRoot.data = pre[pre_start + Left_Length + 1]; //右根节点
root.right = ConstructBTree(RightRoot, pre , pre_start + Left_Length + 1 , pre_start + Left_Length
+ Right_Length - 1, inorder, pos + 1 , inorder_end);
}
return root;
}
public static int FindPos(int num, int arr[]) {
int i = 0;
if(arr != null) {
while(arr[i] != num)
i++;
if(arr[i] == num)
return i;
}
return -1;
}
/*后序遍历*/
public static void LastOrder(TreeNode head) {
if( head != null) {
LastOrder(head.left);
LastOrder(head.right);
System.out.println(head.data);
}
}
public static void main(String[] args) {
TreeNode tnode = RebuildBinaryTree();
LastOrder(tnode);
}
}
费了好半天劲才弄出来，有两点感想：
1.如上图代码中被注释掉的打印语句一样，有时调试程序中的逻辑错误，尤其是令人头大的递归，添加打印语句比单步调试更为简单直白，不然，单步跟踪，调着调着就被绕进去了（智商不高，见谅！）
2.虽然这次是参考着剑指offer上的答案弄出来的，但是还是颇有感触。一定要敢想，坚信一个道理：一切反动派都是纸老虎。尤其是递归，要注意函数的参数。有时候最简单的思路，往往容易被忽视。继续努力！
今天晚上，在牛客网上做剑指offer的题的时候，发现其实自己之前写的代码还可以继续精简一点，看着思路更清晰。
package com.study;
/*
* 根据二叉树的前序遍历和中序遍历结果重建二叉树
* 并输出其头节点。假设前序遍历和中序遍历结果中没有重复数字
* 前序遍历序列：{1，2，4，7，3，5，6，8}
* 中序遍历序列：{4，7，2，1，5，3，8，6}
* **/
class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode() {
}
}
public class suanfa4 {
private static int[] arr1 = {1,2,4,7,3,5,6,8};
private static int[] arr2 = {4,7,2,1,5,3,8,6};
public static TreeNode RebuildBinaryTree() {
TreeNode head = null;
//head = ConstructBTree( head ,arr1, 0, 7, arr2, 0, 7);
head = ConstructBTree(arr1, 0, 7, arr2, 0, 7);
return head;
}
public static TreeNode ConstructBTree(int[] pre, int pre_start, int pre_end,
int[] inorder, int inorder_start, int inorder_end) {
if(pre_start > pre_end || pre_end > pre.length)
return null;
TreeNode root = new TreeNode();
root.data = pre[pre_start]; //找到根节点
root.left = root.right = null;
int pos = FindPos(root.data, inorder); //在中序遍历的数组中找到根节点的位置
int Left_Length = pos - inorder_start;
int Right_Length = inorder_end - pos;
if( Left_Length > 0) { //存在左子树
root.left = ConstructBTree (pre , pre_start + 1, pre_start + Left_Length, inorder,
inorder_start , pos - 1);
}
if( Right_Length > 0) { //存在右子树
root.right = ConstructBTree(pre , pre_start + Left_Length + 1 , pre_start + Left_Length
+ Right_Length, inorder, pos + 1 , inorder_end);
}
return root;
}
public static int FindPos(int num, int arr[]) {
int i = 0;
if(arr != null) {
while(arr[i] != num)
i++;
if(arr[i] == num)
return i;
}
return -1;
}
/*后序遍历*/
public static void LastOrder(TreeNode head) {
if( head != null) {
LastOrder(head.left);
LastOrder(head.right);
System.out.println(head.data);
}
}
public static void main(String[] args) {
TreeNode tnode = RebuildBinaryTree();
LastOrder(tnode);
}
}