python3 解法, 执行用时: 48 ms, 内存消耗: 20.9 MB, 提交时间: 2023-04-22 12:38:15

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

'''
使用一个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

java 解法, 执行用时: 3 ms, 内存消耗: 42.9 MB, 提交时间: 2023-04-22 12:37:39

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<List<Integer>> ans;

    public List<List<Integer>> BSTSequences(TreeNode root) {
        ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        // 如果 root==null 返回 [[]]
        if (root == null) {
            ans.add(path);
            return ans;
        }
        List<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // 开始进行回溯
        bfs(queue, path);
        return ans;
    }

    /**
     * 回溯法+广度优先遍历.
     */
    private void bfs(List<TreeNode> queue, List<Integer> path) {
        // queue 为空说明遍历完了，可以返回了
        if (queue.isEmpty()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 将 queue 拷贝一份，用于稍后回溯
        List<TreeNode> copy = new ArrayList<>(queue);
        // 对 queue 进行循环，每循环考虑 “是否 「将当前 cur 节点从 queue 中取出并将其左右子
        // 节点加入 queue ，然后将 cur.val 加入到 path 末尾」 ” 的情况进行回溯
        for (int i = 0; i < queue.size(); i++) {
            TreeNode cur = queue.get(i);
            path.add(cur.val);
            queue.remove(i);
            // 将左右子节点加入队列
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
            bfs(queue, path);
            // 恢复 path 和 queue ，进行回溯
            path.remove(path.size() - 1);
            queue = new ArrayList<>(copy);
        }
    }
}