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

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

样例
给出前序遍历:
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 (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);
}
}