剑指Offer(Python多种思路实现):重建二叉树

剑指Offer(Python多种思路实现):重建二叉树 面试7题： 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 解题思路一：递归 # 7重建二叉树 【递归】 class TreeNode: # 先定义树的基本结构 def __init__(self, x): self.val=x self.left=None self.righ 在计算机科学领域，二叉树是一种特殊的图结构，它的每个节点最多只有两个子节点，通常分为左子节点和右子节点。重建二叉树是指根据给定的两种遍历序列（如前序遍历和中序遍历）来恢复原始二叉树的数据结构。这个过程在面试中常常作为算法题出现，用来考察候选人的逻辑思维和编程能力。在这个问题中，我们有两个关键的遍历序列：前序遍历和中序遍历。 **前序遍历**的顺序是根节点 -> 左子树 -> 右子树。在给定的前序遍历序列{1,2,4,7,3,5,6,8}中，第一个元素1是根节点。 **中序遍历**的顺序是左子树 -> 根节点 -> 右子树。在给定的中序遍历序列{4,7,2,1,5,3,8,6}中，根节点1将序列分为了两部分：左子树{4,7,2}和右子树{5,3,8,6}。 **解题思路一：递归** 在递归解法中，首先我们需要创建一个`TreeNode`类来表示二叉树的节点，包含节点值、左子节点和右子节点： ```python class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None ``` 接下来，我们可以实现重建二叉树的函数`reConstructBinaryTree`。递归的基线条件是如果前序遍历或中序遍历为空，那么返回None，表示没有树。对于非空输入，我们首先创建根节点，然后找到根节点在中序遍历中的位置，这将中序遍历分割成两部分。接着，我们分别对左右子树进行递归调用。 ```python class Solution: def reConstructBinaryTree(self, pre, tin): if not pre or not tin: return None root = TreeNode(pre[0]) val = tin.index(pre[0]) root.left = self.reConstructBinaryTree(pre[1:val+1], tin[:val]) root.right = self.reConstructBinaryTree(pre[val+1:], tin[val+1:]) return root ``` **解题思路二：空间复杂度更低的解法** 递归方法虽然直观，但可能会导致较大的栈空间消耗。另一种方法是采用迭代，使用一个辅助栈来减少空间复杂度。这里使用了`buildTree`函数，它会根据给定的前序遍历和中序遍历构建二叉树。我们需要一个辅助函数`build(stop)`，它用于构建以`stop`为根节点的子树。在`buildTree`函数中，我们将前序遍历和中序遍历反转，因为我们要从根节点开始构建。 ```python class Solution: def buildTree(self, preorder, inorder): def build(stop): if inorder and inorder[-1] != stop: root = TreeNode(preorder.pop()) root.left = build(root.val) inorder.pop() root.right = build(stop) return root preorder.reverse() inorder.reverse() return build(None) ``` 在这个迭代版本中，我们维护了一个栈，每次从栈顶弹出一个元素，构建相应的子树，直到遍历完所有节点。这种方法避免了递归带来的额外空间开销。 重建二叉树是一个典型的二叉树问题，通过结合前序遍历和中序遍历的信息，可以有效地恢复出原始的二叉树结构。无论是递归还是迭代解法，都需要理解两种遍历序列之间的关系，并能有效地利用这些信息进行构造。在实际编程过程中，应根据具体场景选择合适的算法，考虑时间复杂度和空间复杂度的平衡。