仓库源文站点原文


title: '算法:重建二叉树' cover: https://img.paulzzh.com/touhou/random?7 categories: 算法题目 date: 1996-07-27 08:00:02 tags: [算法题目, 二叉树]

toc: true

<br/>

<!--more-->

重建二叉树

重建二叉树

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

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

例如:

输入前序遍历序列{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;
    }
}