【105. 从前序与中序遍历序列构造二叉树】——【剑指 Offer 07. 重建二叉树】

2021年11月25日 阅读数:4
这篇文章主要向大家介绍【105. 从前序与中序遍历序列构造二叉树】——【剑指 Offer 07. 重建二叉树】,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

【105. 从前序与中序遍历序列构造二叉树】/ 【剑指 Offer 07. 重建二叉树】java

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。数组

示例 1:
【105. 从前序与中序遍历序列构造二叉树】——【剑指 Offer 07. 重建二叉树】_中序遍历ide

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:函数

Input: preorder = [-1], inorder = [-1]
Output: [-1]

提示:优化

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均无重复元素
  • inorder 均出如今 preorder
  • preorder 保证为二叉树的前序遍历序列
  • inorder 保证为二叉树的中序遍历序列

树的三种遍历方式:ui

以根节点的遍历位置来分:code

前/先序遍历(根-左-右):blog

​ 先遍历根节点;递归

​ 随后递归地遍历左子树;索引

​ 最后递归地遍历右子树。

中序遍历(左-根-右):

​ 先递归地遍历左子树;

​ 随后遍历根节点;

​ 最后递归地遍历右子树。

后序遍历(左-右-根):

​ 先递归地遍历左子树;

​ 随后递归地遍历右子树;

​ 最后遍历根节点。

分析:

由前序遍历和中序遍历的特性可知:前序遍历的第一个节点即为树的根节点,中序遍历中,根节点前的为根节点的左子树,根节点后的为根节点的右子树,故咱们能够递归的构造每一个节点的左右子树

解法一:

递归构造每一个节点前序遍历 preorder 与中序遍历 inorder数组,若数组为空,则该节点为null。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    // 递归终止条件
    if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) 
        return null;

    // 一、根据前序遍历数组preorder设置当前根节点
    int root = preorder[0];
    TreeNode tn = new TreeNode(root);

    // 二、设置当前节点左子树
    // 获取当前节点的左子树的长度,根节点在中序遍历中的索引即为其左子树的长度
    int index = getIndex(inorder, root);
    // 2.1 获取左子树的前序遍历和中序遍历数组
    // 先序遍历中,根节点后index个元素为左子树,下标0的元素是根节点,故这里构造的当前节点的前序遍历节点数组的范围为[1, index]
    int[] leftPreorder = Arrays.copyOfRange(preorder, 1, 1 + index);
    // 中序遍历中,根节点前的为左子树,故当前节点的中序遍历数组范围为[0, index - 1]
    int[] leftInorder = Arrays.copyOfRange(inorder, 0, index);
    tn.left = buildTree(leftPreorder, leftInorder);

    // 三、设置当前节点右子树
    // 先序遍历中,左子树元素后紧接着就是右子树元素,故范围为[1 + index, preorder.length - 1]
    int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + index, preorder.length);
    // 中序遍历中,根节点后的元素为右子树的中序遍历结果,故范围为[index + 1, inorder.length - 1]
    int[] rightInorder = Arrays.copyOfRange(inorder, index + 1, inorder.length);
    tn.right = buildTree(rightPreorder, rightInorder);
    return tn;
}

/**
  * 从中序遍历数组中获取根节点的索引,也即左子树的长度
  * @param a
  * @param target
  * @return
  */
public int getIndex(int[] a, int target) {
    for (int i = 0; i < a.length; i++) {
        if (target == a[i])     return i;
    }
    return -1;
}

解法二:对解法一的优化

解法一存在的问题:

  • 对每一个节点,都要构造其左右子树的前序、中序数组,开销大
  • 对于构建的每一个中序数组,都要求遍历求对应根节点的索引,但本质都是初始的中序数组

优化:

  • 对每一个节点,不构造其左右子树的前、中序数组,而是经过指明索引的范围来实现
  • 对于遍历中序数组,由map集合来代替
Map<Integer, Integer> map = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0)   return null;

    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }

    return build(preorder, 0, preorder.length- 1, inorder, 0, inorder.length - 1);
}

/**
 * @param preorder  当前节点的前序遍历数组
 * @param pleft     当前节点的前序遍历数组的起始索引
 * @param pright    当前节点的前序遍历数组的终止索引
 * @param inorder   当前节点的中序遍历数组
 * @param ileft     当前节点的中序遍历数组的起始索引
 * @param iright    当前节点的中序遍历数组的终止
 * @return
 */
private TreeNode build(int[] preorder, int pleft, int pright, int[] inorder, int ileft, int iright) {
    // 终止条件,也能够是ileft > iright, 或二者的 || 关系
    if (pleft > pright)     return null;
    
    // 一、设置当前根节点
    int root = preorder[pleft];
    TreeNode tn = new TreeNode(root);
    
	// 计算当前节点左子树的长度
    int index = map.get(root);
    int len = index - ileft;
    
    // 三、递归调用,获取当前节点的左子树 获取左子树的前序遍历和中序遍历数组
    // 先序遍历的范围为[pleft + 1, pleft + len]
    // 中序变量的范围为[ileft, index - 1],为何是这样,请先看解法一,缘由都同样
    tn.left = build(preorder, pleft + 1, pleft + len , inorder, ileft, index - 1);

    // 三、设置当前节点右子树
    // 先序遍历范围:左子树右边界 + 1:[pleft + len + 1]
    // 中序遍历范围:[index + 1, iright]
    tn.right = build(preorder, pleft + len + 1, pright, inorder, index + 1, iright);

    return tn;
}

方案三:

Map<Integer, Integer> map = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0)   return null;

    for (int i = 0; i < inorder.length; i++) {
        map.put(inorder[i], i);
    }

    return build(preorder, 0, preorder.length- 1, 0);
}

/**
 * 方案三:继续优化
 *
 *  方案二的递归方法一共有6个参数(数组 + 左右边界) * 2
 *  可是,若是去除掉第一行的return语句,咱们实际用到的只有三个值:
 *      preorder + pleft :用来求root节点
 *      ileft :用来求root节点左子树的长度
 *  也就是说剩下的三个参数:pright、inorder、iright没用,故咱们能够将其优化调,
 *  但同时,咱们须要一个终止条件,故pright和iright必须保留其中的一个,
 *  优化后的递归函数以下:
 *      TreeNode build(int[] preorder, int pleft, int pright, int ileft)
 *  或者
 *      TreeNode build(int[] preorder, int pright, int ileft, int ileft)
 *      此时,递归终止条件为 ileft > iright
 */
private TreeNode build(int[] preorder, int pleft, int pright, int ileft) {
    if (pleft > pright)     return null;
    // 一、设置当前根节点
    int root = preorder[pleft];
    TreeNode tn = new TreeNode(root);

    // 二、设置当前节点左子树
    int index = map.get(root);
    int len = index - ileft;
    // 2.1 获取左子树的前序遍历和中序遍历数组
    tn.left = build(preorder, pleft + 1, pleft + len, ileft);

    // 三、设置当前节点右子树
    tn.right = build(preorder, pleft + len + 1, pright, index + 1);

    return tn;
}
只有经历过,才会懂得了!