美文网首页leetcode日记
经典问题剖析-由前序、中序遍历序列构造二叉树(java/kotl

经典问题剖析-由前序、中序遍历序列构造二叉树(java/kotl

作者: 半匣烛火 | 来源:发表于2020-11-22 16:11 被阅读0次

一、题目

根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
示例:给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
    3
   / \
  9  20
    /  \
   15   7

二、递归解法

1. 解题思路

清楚前序遍历和中序遍历的过程:

  • 前序遍历:根、左、右
  • 中序遍历:左、根、右
  • 将前序、中序序列做如下图切割,可以看到是明显的递归调用
前序、中序序列分割图
  • 前序序列中,preOrder[preLeft]为根节点,通过值找到根节点在中序序列中的index,记为pIndex。由于树中没有重复的元素,这个过程可以使用一个hash表存储index,节点值value作为hashKey,index作为hashValue
  • 通过根节点分割的左右子树边界通过preLeft、preRight、inLeft、inRight、pIndex表示,得到左右子树的前序、中序序列。其中中序遍历的左右子树的边界很容就知道是[inLeft,pIndex - 1][pIndex + 1, inRight];前序遍历中,左子树的右边界比较不好一眼看出来,我们可以稍微计算一下,左子树右边界 - (preLeft + 1) = pIndex -1 - inLeft,由这个公式可得出左子树右边界 = pIndex - inLeft + preLeft,自然而然右子树的左边界就是pIndex - inLeft + preLeft + 1,所以前序遍历左右子树的边界就是[preLeft + 1, pIndex - inLeft + preLeft][pIndex - inLeft + preLeft + 1, preRight]。不要嫌麻烦,其实这道题关键就是边界值的表示,没有什么难的。
  • 递归结束条件:preLeft > preRight,相等的时候就是叶子结点。

2. 编码

由解题思路,很容易写出此题的递归解法代码。
示例代码:

class BTreeNode(val value: Int) {
    var left: BTreeNode? = null
    var right: BTreeNode? = null
}

fun buildBTreeByPreOrderAndInOrder(preOrder: IntArray, inOrder: IntArray): BTreeNode? {
    val inOrderIndexHashMap = mutableMapOf<Int, Int>()
    inOrder.forEachIndexed { index, data ->
        inOrderIndexHashMap[data] = index
    }
    return buildBTreeNode(preOrder, inOrderIndexHashMap, 0, preOrder.size - 1, 0, inOrder.size - 1)
}

fun buildBTreeNode(preOrder: IntArray, indexMap: MutableMap<Int, Int>, preOrderLeft: Int, preOrderRight: Int, inOrderLeft: Int, inOrderRight: Int): BTreeNode? {
    if (preOrderLeft > preOrderRight) {
        return null
    }
    //根节点
    val root = BTreeNode(preOrder[preOrderLeft])
    //通过跟节点的value值找在inOrder中的index
    val index = indexMap[preOrder[preOrderLeft]] ?: return null
    //找左子树的在preOrder和inOrder中的左右index

    //左子树 在preOrder中的左右index
    val leftChildTreeOnPreOrderIndexLeft = preOrderLeft + 1
    val leftChildTreeOnPreOrderIndexRight = index - inOrderLeft + preOrderLeft
    //左子树 在inOrder中的左右index
    val leftChildTreeOnInOrderIndexLeft = inOrderLeft
    val leftChildTreeOnInOrderIndexRight = index - 1


    //右子树 在preOrder中的左右index
    val rightChildTreeOnPreOrderIndexLeft = leftChildTreeOnPreOrderIndexRight + 1
    val rightChildTreeOnPreOrderIndexRight = preOrderRight
    //右子树 在inOrder中的左右index
    val rightChildTreeOnInOrderIndexLeft = index + 1
    val rightChildTreeOnInOrderIndexRight = inOrderRight

    root.left = buildBTreeNode(preOrder, indexMap, leftChildTreeOnPreOrderIndexLeft, leftChildTreeOnPreOrderIndexRight, leftChildTreeOnInOrderIndexLeft, leftChildTreeOnInOrderIndexRight)
    root.right = buildBTreeNode(preOrder, indexMap, rightChildTreeOnPreOrderIndexLeft, rightChildTreeOnPreOrderIndexRight, rightChildTreeOnInOrderIndexLeft, rightChildTreeOnInOrderIndexRight)
    return root
}

3. 时空复杂度分析

时间复杂度:数组中每个值都要访问构建二叉树节点,所以时间复杂度为O(N)
空间复杂度:使用Hash表存储根节点的index,需要O(N)的空间,最多有O(logN)个函数调用,所以空间复杂度是O(N)

四、总结

  • 此题难度中等
  • 经典题目,关键是找到根节点、左、右子树边界分别在在前序、中序序列中的index、leftIndex、rightIndex即可

leetcode传送门:105. 从前序与中序遍历序列构造二叉树

相关文章

网友评论

    本文标题:经典问题剖析-由前序、中序遍历序列构造二叉树(java/kotl

    本文链接:https://www.haomeiwen.com/subject/mvvuiktx.html