07:重建二叉树

发表于 | 分类于

题目07：重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

举例说明

输入 ：前序遍历序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍历序列｛4, 7, 2, 1, 5, 3, 8，6}
重建出下所示的二叉树并输出它的头结点。

1
2
3
4
5
6
7
      1
   /     \
  2       3
 /       / \
4       5   6
 \         /
  7       8

思路

整个的思路是：前序定根，中序分左右。

  • 先序遍历序列的第一个数字是根结点值
  • 中序遍历中根结点的左边序列是左子树，右边序列是右子树

解题是特别还需要处理不符合条件的情况：序列为空的情况；两序列元素个数不同的情况；两序列中元素不相同的情况。

步骤

  1. 前序第一个数是根，找到根
  2. 用根的value在中序遍历找到根（同一个），记下根在中序遍历的index
  3. 递归调用建立左右子树

代码实现

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
public class _07 {
	public static class BinaryTreeNode {
		int value;
		BinaryTreeNode left;
		BinaryTreeNode right;
		public BinaryTreeNode() {
		}
		public BinaryTreeNode(int value) {dengl
			this.value = value;
		}
	}

	public static BinaryTreeNode construct(int[] preorder, int[] inorder) {
		//1. 两个数组都不能为空 2. 都有数据 3. 数据的数目相同
		if (preorder == null || inorder == null || preorder.length != inorder.length || inorder.length < 1) {
			return null;
		}
		return construct(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
	}
	/**
	 * @param preorder 前序遍历
	 * @param ps : PreStart      前序遍历的开始位置
	 * @param pe : PreEnd      前序遍历的结束位置
	 * @param inorder  中序遍历
	 * @param is       中序遍历的开始位置
	 * @param ie       中序遍历的结束位置
	 * @return 树的根结点
	 */
	public static BinaryTreeNode construct(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) {
		if (ps > pe) {// 开始位置大于结束位置说明已经没有需要处理的元素了
			return null;
		}
		int value = preorder[ps];// 取前序遍历的第一个数字，就是当前的根结点
		
		int index = is;	
		while (index <= ie && inorder[index] != value) {
			index++;// 在中序遍历的数组中找根结点的位置
		}
		// 如果在整个中序遍历的数组中没有找到，说明输入的参数是不合法的，抛出异常
		if (index > ie) {
			throw new RuntimeException("Invalid input");
		}

		//用前序遍历得到的value的值  创建当前的根结点
		BinaryTreeNode node = new BinaryTreeNode(value);
		// 递归构建当前根结点的左子树，左子树的元素个数：index-is+1个
		// 左子树对应的 前序遍历的位置在[ps+1, ps+ index-is（加上左子树长度-1）]
		// 左子树对应的 中序遍历的位置在[is, index-1]
		node.left = construct(preorder, ps + 1, ps + index - is, inorder, is, index - 1);
		// 递归构建当前根结点的右子树，右子树的元素个数：ie-index个
		// 右子树对应的 前序遍历的位置在[ps+  index-is+1（加上右子树长度-1）, pe]
		// 右子树对应的 中序遍历的位置在[index+1, ie]
		node.right = construct(preorder, ps + index - is + 1, pe, inorder, index + 1, ie);	
		return node;// 返回创建的树的 根结点
	}

	// for test:中序遍历二叉树
	public static void printTree(BinaryTreeNode root) {
		if (root != null) {
			printTree(root.left);
			System.out.print(root.value + " ");
			printTree(root.right);
		}
	}
	public static void main(String[] args) {
        // 普通二叉树
        //              1
        //           /     \
        //          2       3
        //         /       / \
        //        4       5   6
        //         \         /
        //          7       8
		int[] preorder = { 1, 2, 4, 7, 3, 5, 6, 8 };
		int[] inorder = { 4, 7, 2, 1, 5, 3, 8, 6 };
		BinaryTreeNode root = construct(preorder, inorder);
		printTree(root);
	}
}

输出： 

1
4 7 2 1 5 3 8 6
> >