原文链接: https://leetcode-cn.com/problems/bst-sequences-lcci

英文原文

A binary search tree was created by traversing through an array from left to right and inserting each element. Given a binary search tree with distinct elements, print all possible arrays that could have led to this tree.

Example:
Given the following tree:

        2
       / \
      1   3

Output:

[
   [2,1,3],
   [2,3,1]
]

中文题目

从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉搜索树，输出所有可能生成此树的数组。

 

示例：
给定如下二叉树

        2
       / \
      1   3

返回：

[
   [2,1,3],
   [2,3,1]
]

通过代码

高赞题解

搜索

• 使用一个queue存储下个所有可能的节点
• 然后选择其中一个作为path的下一个元素
• 递归直到queue元素为空
• 将对应的path加入结果中
• 由于二叉搜索树没有重复元素, 而且每次递归的使用元素的顺序都不一样, 所以自动做到了去重

  class Solution:
      def BSTSequences(self, root: TreeNode) -> List[List[int]]:
          if not root:
              return [[]]
          res = []
          def findPath(cur, q, path):
              if cur.left:
                  q.append(cur.left)
              if cur.right:
                  q.append(cur.right)
              if not q:
                  res.append(path)
                  return
              for i, nex in enumerate(q):
                  newq = q[:i] + q[i + 1:]
                  findPath(nex, newq, path + [nex.val])
          findPath(root, [], [root.val])
          return res

---

统计信息

通过次数	提交次数	AC比率
7021	14733	47.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言