不忘初心

少年,专心练剑吧

前序遍历和中序遍历树构造二叉树

发表于 更新于 分类于

题目

根据前序遍历和中序遍历构造二叉树.
注意：这里默认二叉树中的值都是唯一的。

样例
给出前序遍历：
int[] preOrder = { 6, 10, 4, 3, 1, 0, 7, 12 };
中序遍历：
int[] inOrder = { 4, 10, 3, 1, 6, 12, 7, 0 };

返回如下的树:

1
2
3
4
5
6
7
        _______6______ 
       /               \ 
    __10__             __0__ 
   /      \           / 
  4        3        7 
            \      / 
             1    12

分析

首先还是对数组进行判断，如果前序遍历数组为null或后续遍历数组为null，则return null;
前序遍历的第一个结点就是二叉树的根结点。
中序遍历从第一个到根结点之前的结点序列为左子树，中序遍历中根结点之后的结点序列为右子树。
然后使用递归来处理根结点的左子树和右子树。

代码（Java）

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
   public TreeNode buildTree(int[] preorder, int[] inorder) {
	if (preorder == null || inorder == null) {
		return null;
	}
	return ConstructCore(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}

public TreeNode ConstructCore(int[] preOrder, int[] inOrder, int startPreorder, int endPreorder,
		int startInorder, int endInorder) {

	if (startPreorder > endPreorder || startInorder > endInorder) {
		return null;
	}
	TreeNode root = new TreeNode(preOrder[startPreorder]);

	int divider = 0;
	while (divider <= endInorder && inOrder[divider] != root.val) {
		divider++;
	}

	int offSet = divider - startInorder - 1;
	root.left = ConstructCore(preOrder, inOrder, startPreorder + 1, startPreorder + 1 + offSet, startInorder,
			startInorder + offSet);
	root.right = ConstructCore(preOrder, inOrder, startPreorder + offSet + 2, endPreorder, divider + 1, endInorder);

	return root;
}

补充：中序遍历二叉树和前序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
   // 中序遍历二叉树
public static void inorder(TreeNode root) {
	if (root != null) {
		preorder(root.left);
		System.out.print(root.val + " ");
		preorder(root.right);
	}
}

// 先序遍历二叉树
public static void preorder(TreeNode root) {
	if (root != null) {
		System.out.print(root.val + " ");
		preorder(root.left);
		preorder(root.right);
	}
}