推理二叉树

标签: 树 数组 哈希表 分治 二叉树

难度: Medium

某二叉树的先序遍历结果记录于整数数组 preorder，它的中序遍历结果记录于整数数组 inorder。请根据 preorder 和 inorder 的提示构造出这棵二叉树并返回其根节点。

注意：preorder 和 inorder 中均不含重复数字。

示例 1：

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]

输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Submission

运行时间: 224 ms

内存: 19.1 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

        def build(pstart, pend, istart, iend):
            if pstart > pend:
                return

            root_val = preorder[pstart]
            root = TreeNode(root_val)
            index = istart
            for i in range(istart, iend+1):
                if inorder[i] == root_val:
                    index = i
                    break
            
            left_length = index - istart
            root.left = build(pstart+1, pstart+left_length, istart, istart+left_length)
            root.right = build(pstart+left_length+1, pend, istart+left_length+1, iend)
            return root

        return build(0, len(preorder)-1, 0, len(inorder)-1)

Explain

此题解采用的是递归的方式来构建二叉树。首先根据前序遍历的第一个元素确定树的根节点，然后在中序遍历中找到该根节点，从而区分出左子树和右子树的中序遍历。利用中序遍历中左、右子树的长度，可以相应地从前序遍历中划分出左右子树的前序遍历序列。这样，递归地对左右子树进行相同的构建过程，直到所有的子树都被正确构建。

时间复杂度: O(n^2)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

        def build(pstart, pend, istart, iend):
            if pstart > pend:
                return

            # 找到根节点的值，并创建根节点
            root_val = preorder[pstart]
            root = TreeNode(root_val)

            # 在中序遍历中找到根节点的索引
            index = istart
            for i in range(istart, iend+1):
                if inorder[i] == root_val:
                    index = i
                    break
            
            # 计算左子树的长度
            left_length = index - istart

            # 递归构建左子树
            root.left = build(pstart+1, pstart+left_length, istart, istart+left_length)
            # 递归构建右子树
            root.right = build(pstart+left_length+1, pend, istart+left_length+1, iend)
            return root

        return build(0, len(preorder)-1, 0, len(inorder)-1)

Explore

在题解中使用线性搜索而不使用哈希表来查找中序遍历数组中的根节点索引，可能是出于简化代码的考虑或假设输入规模较小而搜索开销不大。使用哈希表虽然可以将索引查找的时间复杂度降低到O(1)，提高效率，但会增加额外的空间复杂度。对于小规模数据，这种时间复杂度的提升可能不明显，而额外的空间复杂度则可能成为负担。然而，在处理大规模数据时，使用哈希表来优化查找效率确实是一种更优的选择。

在递归构建二叉树的过程中，`pstart+left_length`是左子树在前序遍历序列中的最后一个元素的位置，因此这确定了左子树的边界。右子树在前序遍历中的开始位置是`pstart+left_length+1`，这里的+1表明跳过了当前的根节点，直接移动到右子树的第一个元素。这是因为前序遍历的顺序是根节点后紧跟左子树，再跟右子树，且左子树的长度正是由中序遍历中的根节点位置决定。

递归函数`build`会在`pstart`大于`pend`时返回`None`，这发生在二叉树的某个分支不存在任何节点时，比如某个节点不存在左子树或右子树。在这种情况下，递归的边界条件`pstart > pend`成立，意味着不存在更多的节点可以用来构建子树，因此返回`None`表示该子树为空。这确实意味着在某些情况下子树可能不存在，这在不完全二叉树中是常见的情形。

在这种树的构建方法中，优化递归过程确实可以提高算法性能。然而，尾递归优化在这个场景下可能不太适用，因为树的构建本质上需要处理两个递归分支（左子树和右子树），并且它们的处理依赖于前一个递归的结果。这不符合尾递归的条件，因为尾递归要求最后一个操作必须是递归调用本身。更有效的优化方法可能包括使用哈希表来优化中序遍历的索引查找，从而减少查找时间，或者重新设计递归逻辑，减少不必要的计算和空间消耗。