程序员面试金典 - 面试题 04.09. 二叉搜索树序列

题目难度: 困难

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

示例：

给定如下二叉树

        2
       / \
      1   3

返回：

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

题目思考

1. 从左向右遍历, 那么根节点一定是数组第一个元素, 可以利用到这一特性吗?
2. 对于数组某个元素而言, 其有效插入位置可能有哪些?

解决方案

思路

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

复杂度

• 时间复杂度 O((N^2)*(2^N)): 对于每个节点都要考虑其左右子节点, 所以 2^N 次递归; 每个递归里面也要遍历集合, 以及集合需要求差集, 这部分是 O(N^2)
• 空间复杂度 O(N): 递归的栈的消耗, 以及一个数组一个集合, 其元素数目都是 N (不考虑结果数组的占用)

代码

class Solution:
    def BSTSequences(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return [[]]
        res = []

        def findPath(curNode, nextValidNodes, path):
            if curNode.left:
                nextValidNodes.add(curNode.left)
            if curNode.right:
                nextValidNodes.add(curNode.right)
            if not nextValidNodes:
                # 已经没有候选节点了, 将当前路径加入结果中
                res.append(path)
                return
            for nex in nextValidNodes:
                # 使用当前nex节点的值, 继续递归
                findPath(nex, nextValidNodes - {nex}, path + [nex.val])

        findPath(root, set(), [root.val])
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊