算法:重建二叉树

重建二叉树

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字

例如:

输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

分析

根据二叉树前序遍历和中序遍历的特征进行重建, 具体过程为：

1. 根据前序序列第一个结点确定根结点
2. 根据根结点在中序序列中的位置分割出左右两个子序列
3. 对左子树和右子树分别递归使用同样的方法继续分解

即使用类似于自顶向下的归并排序对二叉树进行重构;

例如：

前序序列{1,2,4,7,3,5,6,8} = pre

中序序列{4,7,2,1,5,3,8,6} = in

1. 根据当前前序序列的第一个结点确定根结点，为1
2. 找到 1 在中序遍历序列中的位置，为 in[3]
3. 切割左右子树，则 in[3] 前面的为左子树， in[3] 后面的为右子树
4. 则切割后的左子树前序序列为：{2,4,7}，切割后的左子树中序序列为：{4,7,2}；[前序遍历的序列长度和中序遍历长度相同]
5. 切割后的右子树前序序列为：{3,5,6,8}，切割后的右子树中序序列为：{5,3,8,6}；[前序遍历的序列长度和中序遍历长度相同]
6. 对子树分别使用同样的方法分解

代码

public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return helper(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    public TreeNode helper(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        if (startIn > endIn || startPre > endPre) return null;

        // 先序遍历节点
        TreeNode curRoot = new TreeNode(pre[startPre]);
        for (int i = startIn; i <= endIn; ++i) {
            // 找到中序遍历节点, 此节点左右即为curRoot的左右节点
            if (in[i] == curRoot.val) {
                // 对于左子树而言
                // 中序遍历子树范围: [startIn, i - 1]
                // 先序遍历子树范围: [startPre + 1, startPre + 1 + (i - 1 - startIn)]
                curRoot.left = helper(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
                // 右子树同理
                curRoot.right = helper(pre, i - startIn + startPre + 1, endPre, in, i + 1, endIn);
                break;
            }
        }
        return curRoot;
    }
}