描述

题目描述

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

示例
输入：[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值：{1,2,5,3,4,6,7}

知识点：二叉树，递归，分治，队列
难度：⭐⭐⭐

题解

解题思路

对于这样类似要左右区间分开求出结果的类型的二叉树问题，一般可以用递归

这道理最关键的是：了解前需每次递归求出中序遍历数组中，左区间或右区间的的根节点在中序遍历数组的

其中左右分别递归区间，分别得到左右区间的根节点作为上次根节点的左右子结点，采用了类似分治的思想

除了递归，我们还可以通过队列或栈实现非递归解法

方法一：递归

图解

image-20210715183040582

算法流程：
  • 递归函数功能定义：根据前序和中序遍历获取当前递归的根节点
  • 递归终止条件：前序遍历数组长度为1，直接返回，表示已经递归到最右叶子节点
  • 前序遍历的首元素就是当前递归层次的根节点
  • 确定左右子树的范围 ，从中间向两边查找跟节点索引，从中序遍历中根据根节点的值找到中序遍历数组中根节点的索引
  • 当前根节点的左子节点为左子树的跟节点，拼接、构建二叉树即可
Java 版本代码如下：
import java.util.*;
public class Solution {
    // 递归函数功能定义：根据前序和中序遍历获取当前递归区间的根节点
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre == null || pre.length == 0) {
            return null;
        }
        // 前序遍历的首元素就是当前递归层次的根节点
        int rootVal = pre[0];
        // 当前长度为1，直接返回，表示已经递归到最右叶子节点 
        if(pre.length == 1) {
            return new TreeNode(rootVal);
        }
        int rootIndex = 0;
        // 确定左右子树的范围
        // 从中间向两边查找跟节点索引
        for(int i = 0; i < in.length; i++) {
            if(rootVal == in[i]) {
                // 中序遍历数组中根节点的索引
                rootIndex = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootVal);
        // 左右分别递归区间，分别得到左右区间的根节点作为上次根节点的左右子结点
        // copyOfRange为左开右闭 [)， 即包括左界限不包括右界限
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, rootIndex + 1), Arrays.copyOfRange(in, 0, rootIndex));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, rootIndex + 1, pre.length), Arrays.copyOfRange(in, rootIndex + 1, in.length));
        return root;
    }
}
Go 版本代码如下：
package main
import . "nc_tools"
func reConstructBinaryTree( pre []int ,  vin []int ) *TreeNode {
    if len(pre)==0{
        return nil
    }
    if len(pre)==1{
        return &TreeNode{pre[0],nil,nil}
    }
    root:=&TreeNode{}
    root.Val=pre[0]
    index:=0
    // 确定左右子树的范围
    // 从中间向两边查找跟节点索引
    for i:=0;i<len(pre);i++{
        if vin[i]==root.Val{
            index=i
            break
        }
    }
    // 左右分别递归区间，分别得到左右区间的根节点作为上次根节点的左右子结点
    root.Left=reConstructBinaryTree(pre[1:index+1],vin[:index])
    root.Right=reConstructBinaryTree(pre[index+1:],vin[index+1:])
    return root
}
复杂度分析：

时间复杂度 O(N)：递归了每个结点，N为结点数
空间复杂度 O(N)：递归所用的栈空间

方法二：迭代

算法流程：
  • 维护一个指针：指向根节点在中序遍历中的索引位置的指针，栈用来保存结点
  • 初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点；
  • 我们依次枚举前序遍历中除了第一个节点以外的每个节点。、
    • 用前序数组一直构建左子树, 即一开始是先走到最左叶子结点，如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的左儿子；连接左子节点
    • 如果 index 恰好指向栈顶节点，即表示到了左下角，这时就需要往上走并处理右子树，此时不断地弹出栈顶节点并向右移动 index，并将当前节点作为最后一个弹出的节点的右儿子；连接右子节点
Java 版本代码如下：
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        // 指向根节点在中序遍历中的索引位置的指针    
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            // 用前序数组一直构建左子树, 即一开始是先走到最左叶子结点
            if (node.val != inorder[inorderIndex]) {
                // 当前节点作为栈顶节点的左儿子结点
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                // 表示到了左下角，这时就需要往上走并处理右子树
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    // 指针往上走，直到碰到节点node有右子节点
                    inorderIndex++;
                }
                // 连接右子结点
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}
复杂度分析：

时间复杂度 O(N)：迭代每个结点
空间复杂度 O(N)：栈用到额外空间