说个常识

如果你学过数据结构，你应该知道：

如果只有前序、中序或后序遍历，是无法唯一确定一棵二叉树的。

这是因为一个前序、中序或后序遍历序列可以对应多棵不同的二叉树。

例如，以下两棵二叉树的前序遍历、中序遍历、后序遍历序列均相同：

      1                1
     / \              / \
    2   3            4   2
   / \                  / \
  4   5                3   5

它们的前序遍历、中序遍历、后序遍历序列都为[1, 2, 4, 5, 3]。

因此，如果只有前序、中序或后序遍历，就无法唯一地构造出原始的二叉树。但如果已知其中任意两种遍历序列，则可以唯一地确定一棵二叉树。

后序 + 中序遍历 构造二叉树 106

可行性

可以使用中序遍历和后序遍历构造一棵二叉树的原因是，中序遍历序列可以将树的节点划分为左子树和右子树两部分，而后序遍历序列可以确定树的根节点以及根节点的左右子树。

下面以一棵简单的二叉树为例，说明如何使用中序遍历和后序遍历构造二叉树。

假设有如下的二叉树：

      4
     / \
    2   5
   / \
  1   3

该二叉树的中序遍历序列是：[1, 2, 3, 4, 5]，后序遍历序列是：[1, 3, 2, 5, 4]。

我们可以首先确定树的根节点是4，然后在中序遍历序列中找到根节点的位置，可以将中序遍历序列分为左子树和右子树两部分，即[1, 2, 3]和[5]。接下来，我们可以根据后序遍历序列中根节点的位置，将后序遍历序列分为左子树和右子树两部分，即[1, 3, 2]和[5]。

然后，我们可以递归地对左子树和右子树进行同样的操作，直到构造出整棵二叉树。具体地，对于左子树，我们可以使用中序遍历序列[1, 2, 3]和后序遍历序列[1, 3, 2]来构造左子树；对于右子树，我们可以使用中序遍历序列[5]和后序遍历序列[5]来构造右子树。

代码

要使用后序遍历和中序遍历构造一棵二叉树，可以按照以下步骤：

1. 后序遍历的最后一个节点是根节点。
2. 在中序遍历中找到根节点的位置，可以将中序遍历序列分为左子树和右子树两部分。
3. 递归地构造右子树。
4. 递归地构造左子树。

下面是一个示例代码，它接受后序遍历和中序遍历序列作为参数，并返回构造出的二叉树的根节点：

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None
        n = postorder.pop()
        i = inorder.index(n)
        root = TreeNode(n)
        root.right = self.buildTree(inorder[i+1:], postorder)
        root.left = self.buildTree(inorder[:i], postorder)
        return root

先取出后序遍历的最后一个节点作为根节点的值，并创建根节点。然后在中序遍历中找到根节点的位置，并将中序遍历序列分为左子树和右子树两部分。接下来递归地构造右子树和左子树，并将它们分别赋值给根节点的right和left属性。

这个方法的时间复杂度是O(n)，其中n是树中节点的个数。因为在每个递归调用中，都要在中序遍历序列中寻找根节点的位置，这需要O(n)的时间复杂度。另外，由于每个节点都会被访问一次，因此总的时间复杂度是O(n)。 下面是一个示例用法：

inorder = [9, 3, 15, 20, 7] postorder = [9, 15, 7, 20, 3] root = Solution().buildTree(inorder, postorder)

这将构造出如下的二叉树：

     3
    / \
   9  20
     / \
    15  7

相关题目

106. 从中序与后序遍历序列构造二叉树 - 力扣（Leetcode）

前序+ 中序遍历 构造二叉树 105

代码

要使用前序遍历和中序遍历构造一棵二叉树，可以按照以下步骤：

1. 前序遍历的第一个节点是根节点。
2. 在中序遍历中找到根节点的位置，可以将中序遍历序列分为左子树和右子树两部分。
3. 递归地构造左子树。
4. 递归地构造右子树。

下面是一个示例代码，它接受前序遍历和中序遍历序列作为参数，并返回构造出的二叉树的根节点：

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None
        n = preorder.pop(0)
        i = inorder.index(n)
        root = TreeNode(n)
        root.left = self.buildTree(preorder,inorder[:i])
        root.right = self.buildTree(preorder,inorder[i+1:])
        return root

在这个实现中，首先取出前序遍历的第一个节点作为根节点的值，并创建根节点。然后在中序遍历中找到根节点的位置，并将中序遍历序列分为左子树和右子树两部分。接下来递归地构造左子树和右子树，并将它们分别赋值给根节点的left和right属性。最后返回根节点即可。

下面是一个示例用法：

preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7] root = Solution().buildTree(preorder, inorder)

这将构造出如下的二叉树：

     3
    / \
   9  20
     / \
    15  7

相关题目

105. 从前序与中序遍历序列构造二叉树 - 力扣（Leetcode）

前序 + 后序

代码

要使用前序遍历和中序遍历构造一棵二叉树，可以按照以下步骤：

1. 前序遍历的第一个节点是根节点。

2. 看是否需要继续往下建树：

   • 看前序列表是否有下一个元素（左子树根节点）

   • 找到左子树根节点在后续遍历中的位置

3. 根据后序遍历中左子树根节点的位置，可以将后序遍历序列分为左子树和右子树两部分。

4. 递归地构造左子树。

5. 递归地构造右子树。

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructFromPrePost(self, preorder, postorder):
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        if len(preorder) > 1:
            i = postorder.index(preorder[1]) + 1
            root.left = self.constructFromPrePost(preorder[1:i + 1], postorder[:i])
            root.right = self.constructFromPrePost(preorder[i + 1:], postorder[i:-1])
        return root

• 首先判断前序遍历结果是否为空，若为空，则直接返回 None。

• 如果前序遍历结果不为空，首先创建根节点。

• 如果前序遍历结果长度大于 1，说明还需要继续往下建树。

  • 找到前序遍历结果的第二个元素在后序遍历结果中的位置，以此来划分左子树和右子树的边界。

    根据前序遍历的性质，前序遍历结果的第二个元素是左子树的根节点。

    根据后序遍历的性质，左子树的最后一个元素是左子树的根节点的前一个元素。

    因此，通过找到前序遍历结果的第二个元素在后序遍历结果中的位置，就可以确定左右子树的边界。

    为什么 仅用一个i就可以确保左右子树划分？ 因为两个遍历列表的长度必然是相同的，根据前序遍历和后续遍历的性质，只要保证后序遍历划分正确，那前序遍历只需要取出对应的长度，就可以保证前序遍历划分是正确的。 前序遍历： [根∣左子树∣右子树][根|左子树|右子树][根∣左子树∣右子树] 后序遍历： [右子树∣左子树∣根][右子树|左子树|根][右子树∣左子树∣根]

• 最后，分别递归构建左子树和右子树，将其作为当前节点的左右子树，并返回根节点即可。

这段代码是一种简洁而易懂的实现方式，但需要注意的是，它假设输入的前序遍历结果和后序遍历结果是合法的，并且不存在重复元素。如果存在重复元素，则需要特殊处理。

注意：

使用前序和后序可以唯一确定一棵树，但是不同的树的前序后序可能是一样的。

比如：

       1                1
      /                  \ 
     2                    2
    / \                 /   \
   3   4               3     4
  /                     \
 5                       5

这两棵树的前序遍历都是[1, 2, 3, 5, 4]，后序遍历都是[5, 3, 4, 2, 1]。

不同的树，前序和后序遍历一样，但是上边的代码默认是建的左边那棵树。

相关题目

889. 根据前序和后序遍历构造二叉树 - 力扣（Leetcode）

108. 将有序数组转换为二叉搜索树

108. 将有序数组转换为二叉搜索树 - 力扣（Leetcode）

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

 

示例 1：

输入： nums = [-10,-3,0,5,9]

输出： [0,-3,9,-10,null,5]

解释： [0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入： nums = [1,3]

输出： [3,1]

解释： [1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

 

提示：

• 1<=nums.length<=1041 <= nums.length <= 10^41<=nums.length<=104

• −104<=nums[i]<=104-104 <= nums[i] <= 10^4−104<=nums[i]<=104

• nums 按 严格递增 顺序排列

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums: 
            return
        i = len(nums) // 2
        root = TreeNode(nums[i])
        root.left = self.sortedArrayToBST(nums[:i])
        root.right = self.sortedArrayToBST(nums[i+1:])
        return root

这段代码实现了将一个升序排列的数组转换为平衡二叉搜索树（BST）的功能。这里的思路是，每次选择中间的元素作为根节点，然后递归地将数组的左半部分和右半部分转换为左子树和右子树。

具体地，首先判断数组是否为空。如果是空数组，则返回None表示该子树为空。否则，找到数组中间的位置，将中间位置的元素作为根节点的值，创建根节点。然后递归地将左半部分和右半部分分别转换为左子树和右子树，并将它们分别赋值给根节点的left和right属性。最后返回根节点即可。

这段代码的时间复杂度是O(n)O(n)O(n)，其中n是数组的长度。因为每个元素都会被访问一次，而在每次递归中都将数组分为两部分，所以总的递归次数是O(logn)O(log n)O(logn)，因此总的时间复杂度是O(nlogn)O(n log n)O(nlogn)。