【算法怎么就这么难——挑战剑指offer】系列04:重建二叉树

1. 题干描述

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

2. 回顾遍历二叉树的三种规则

  • 前序遍历:先自己,再左结点,最后右结点
  • 中序遍历:先左结点,再自己,最后右结点
  • 后序遍历:先左结点,再右结点,最后自己

由此可以获得的规律和解题算法:

  • 前序遍历的第一个结点是root,对于中序遍历的结果中应该是位于中间位置
  • 获得root后,从中序遍历的结果来看,以root切分,可以得到两棵子树
  • 之后继续读前序遍历的结果,对应到中序遍历的结果可以继续分割,直到分割时只有一个叶子结点
  • 以此类推,可以推断出原始的二叉树结构

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
private static int preValueIndex = 0;
public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    //如果子树只有一个结点,证明是叶子
    if (in.length == 1) {
        return new TreeNode(pre[preValueIndex]);
    }
 
    //既然已经过了上面的判断,证明不是叶子节点,可以建立父结点了
    TreeNode thisNode = new TreeNode(pre[preValueIndex]);
    //确定当前遍历的结点在中序遍历的位置
    int inRootValueIndex = ArrayUtils.indexOf(in, pre[preValueIndex]);
    //重建左子树
    TreeNode leftChildren = null;
    if (0 < inRootValueIndex) {
        //移动前序遍历的游标
        preValueIndex++;
        int[] leftSubTree = ArrayUtils.subarray(in, 0, inRootValueIndex);
        leftChildren = reConstructBinaryTree(pre, leftSubTree);
    }
    //重建右子树
    TreeNode rightChildren = null;
    if ((inRootValueIndex + 1) < in.length) {
        //移动前序遍历的游标
        preValueIndex++;
        int[] rightSubTree = ArrayUtils.subarray(in, inRootValueIndex + 1, in.length);
        rightChildren = reConstructBinaryTree(pre, rightSubTree);
    }
 
    //包装两个子树的父结点(即本身)
    thisNode.left = leftChildren;
    thisNode.right = rightChildren;
    return thisNode;
}

4. 变式:不允许使用递归

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
public static TreeNode reConstructBinaryTreeWithoutRecurrence(int[] pre, int[] in) {
    Stack<Entry<int[], TreeNode>> stack = new Stack<>();
    int preValueIndex = 0;
 
    //辅助值,用于标记下一个结点是否应该放到右孩子上
    boolean isRightSubTree = false;
    TreeNode root = null;
    int[] arrPointer = in;
    while (!stack.isEmpty() || (arrPointer != null && arrPointer.length > 0)) {
        while (arrPointer != null && arrPointer.length > 0) {
            TreeNode node = new TreeNode(pre[preValueIndex++]);
            int thisNodeValueIndex = ArrayUtils.indexOf(arrPointer, node.val);
            int[] subarray = ArrayUtils.subarray(arrPointer, 0, thisNodeValueIndex);
            //如果栈不为空,证明该结点有父结点
            if (!stack.isEmpty()) {
                TreeNode parent = stack.peek().getValue();
                //如果右孩子标记为true,则当前结点是从下面的if结构中首次过来的
                if (isRightSubTree) {
                    parent.right = node;
                    isRightSubTree = false;
                }else {
                    parent.left = node;
                }
            }
            //进栈(整体数组和父结点的值)
            stack.push(new Entry<>(arrPointer, node));
            arrPointer = subarray;
            //如果subarray为空数组,证明没有左子树了,跳出while循环
            if (subarray.length == 0) {
                break;
            }
        }
        if (!stack.isEmpty()) {
            Entry<int[],TreeNode> childrenEntry = stack.peek();
            //如果数组长度为1,则该结点为叶子结点,直接弹栈
            //或者:如果此时isRightSubTree也是true,证明本来要去找右子树的,结果没找到,这个值没有被修改
            //这就代表:当前结点已经构建完毕
            boolean childrenIsLeaf = childrenEntry.getKey().length == 1;
            if (childrenIsLeaf || isRightSubTree) {
                stack.pop();
                //如果此时二叉树已经遍历完毕,并且栈内只剩下一个元素,直接返回
                if (preValueIndex == in.length && stack.size() == 1) {
                    return stack.pop().getValue();
                }
            }
            Entry<int[],TreeNode> parentEntry = stack.peek();
            //如果当前的孩子结点是父结点的左孩子,则用父结点的value取索引;右孩子则用孩子结点value取索引
            boolean childrenIsRight = parentEntry.getValue().right == childrenEntry.getValue();
            //这个地方到底使用父结点的value还是子结点的value,要取决于当前子结点是否为右孩子
            int thisNodeValueIndex = ArrayUtils.indexOf(parentEntry.getKey(), 
                    (childrenIsRight ? childrenEntry : parentEntry).getValue().val);
            int[] rightSubTree = ArrayUtils.subarray(parentEntry.getKey(), 
                    thisNodeValueIndex + 1, parentEntry.getKey().length);
            arrPointer = rightSubTree;
            isRightSubTree = true;
        }
    }
 
    return root;
}

发表评论