LeetCode 105. 从前序与中序遍历序列构造二叉树 |

105. 从前序与中序遍历序列构造二叉树

---

题目来源：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

题目

---

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解题思路

---

思路：递归

在这里，先讲一下前序遍历和中序遍历的概念。

• 前序遍历：首先访问根节点，然后遍历左子树，最后遍历右子树。
• 中序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树。

即是说两者的遍历顺序分别为：

• 前序遍历：根节点 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根节点 -> 右子树

根据上面的顺序可以看到，前序遍历中，第一个就是根节点；而中序遍历中，根节点的左侧是左子树，右侧是右子树。根据这个特性，先结合例子看下。

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

在这个例子当中，前序遍历 preorder 的第一个元素 3 即是根节点，再看中序遍历， inorder 中 3 的左边 [9] 即是左子树，而右边 [15, 20, 7] 即是右子树。根据这个思路，就能构造出完整的二叉树。

这里说下具体的思路：

• 首先找到根节点（依据：前序遍历顺序，先遍历根节点）
• 构建根节点的左子树（依据：中序遍历，根节点的左侧为左子树）
• 构建根节点的右子树（依据：中序遍历，根节点的右侧为右子树）

题目中，有个提示：【假设树中没有重复的元素】。依据这个提示，我们在前序遍历中找到的根节点元素，可根据元素值在中序遍历中定位它的位置。

具体的代码实现如下。

代码实现

---

# 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_tree(pre_left, pre_right, in_left, in_right):
            """构建二叉树

            Args:
                pre_left: 前序遍历左边界
                pre_right: 前序遍历右边界
                in_left: 后序遍历左边界
                in_right: 后序遍历右边界
            """
            # 终止条件
            if in_left > in_right:
                return None

            # 根据前序遍历的顺序，第一个元素就是根节点
            pre_root = pre_left
            # 构建根节点
            root = TreeNode(preorder[pre_root])

            # 因为题目提示，假设树中没有重复元素
            # 那么根据根节点的值，在 inorder 中定位
            in_root = inorder.index(root.val)
            # 根据中序遍历的访问顺序，根节点的左边即是左子树，右边是右子树
            # 在这里先得到左子树节点数目
            size_left_subtree = in_root - in_left
            # 构建左子树
            # 在这里中序遍历根节点左边部分的节点（不包含根节点），其实就等同于前序遍历左边界下一位 + size_left_subtree 个节点
            # 即是 in_left 到 inroot 前一位这部分节点，等同于 pre_left 的下一位开始的 size_left_subtree 个元素
            root.left = build_tree(pre_left+1, pre_left+size_left_subtree, in_left, in_root-1)
            # 构建右子树
            # 此时中序遍历根节点右边部分的节点（不包含根节点），对应前序遍历左边界 + 1 + sub_left_subtree 开始到其右边界
            root.right = build_tree(pre_left+1+size_left_subtree, pre_right, in_root + 1, in_right)

            return root

        size = len(inorder)

        return build_tree(0, size-1, 0, size-1)

实现结果

---

实现结果

总结

---

• 首先在根据前序遍历访问的顺序，先找到二叉树的根节点，构建根节点
• 因为题目说明可假设无重复元素，那么可依据上面找到根节点的值，在中序遍历 inorder 中找到其位置。
• 依据中序遍历的访问顺序，可确定当前找到的根节点左侧是左子树，右侧部分是右子树
• 那么根据上面分析的情况，递归构建左子树，右子树。

---

欢迎关注微信公众号《书所集录》