leetcode
leetcode 2801 ~ 2850
二叉搜索树序列

二叉搜索树序列

难度:

标签:

题目描述

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]
]

代码结果

运行时间: 30 ms, 内存: 17.1 MB

/*
 * 思路：
 * 使用Java Stream API来生成所有可能的数组。
 * 和传统方法类似，我们通过递归来生成左右子树的所有可能数组，然后使用Stream的方式进行组合。
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class SolutionStream {
    public List<List<Integer>> BSTSequences(TreeNode root) {
        if (root == null) {
            return Stream.of(new ArrayList<Integer>()).collect(Collectors.toList());
        }
        List<Integer> prefix = new LinkedList<>();
        prefix.add(root.val);
        List<List<Integer>> leftSeq = BSTSequences(root.left);
        List<List<Integer>> rightSeq = BSTSequences(root.right);
        return leftSeq.stream().flatMap(left -> rightSeq.stream().map(right -> {
            List<List<Integer>> results = new ArrayList<>();
            weaveLists(left, right, prefix, results);
            return results;
        })).flatMap(List::stream).collect(Collectors.toList());
    }

    private void weaveLists(List<Integer> first, List<Integer> second, List<Integer> prefix, List<List<Integer>> results) {
        if (first.isEmpty() || second.isEmpty()) {
            List<Integer> result = new LinkedList<>(prefix);
            result.addAll(first);
            result.addAll(second);
            results.add(result);
            return;
        }

        int headFirst = first.remove(0);
        prefix.add(headFirst);
        weaveLists(first, second, prefix, results);
        prefix.remove(prefix.size() - 1);
        first.add(0, headFirst);

        int headSecond = second.remove(0);
        prefix.add(headSecond);
        weaveLists(first, second, prefix, results);
        prefix.remove(prefix.size() - 1);
        second.add(0, headSecond);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

解释

方法:

这道题目要求找到所有可能的数组序列，这些序列能够通过从左到右的插入操作重建给定的二叉搜索树（BST）。解题关键是理解每个节点必须在它的所有子孙节点之前出现。解决这个问题的方法是使用回溯法来模拟这个过程。算法使用一个队列来存储当前可用于插入到序列中的节点，这些节点是已经在序列中的节点的直接子节点。回溯过程中，从队列中选择一个节点，将其添加到当前路径，然后将其子节点添加到队列中，继续递归。每次递归调用后，需要将路径和队列状态回溯到之前的状态，以便尝试其他的选择。

时间复杂度:

O(n!)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么选择使用回溯法来解决这个问题，有没有其他可能的算法可以应用？
▷
回溯法被选择来解决这个问题是因为它能够有效地探索所有可能的节点插入序列，直到找到可以重建原始二叉搜索树的序列。这种方法类似于深度优先搜索，适用于需要遍历多种可能状态的问题。在每一步中，算法都尝试将一个节点添加到序列中，并递归地尝试所有后续可能性，然后撤销这一步骤（回溯），尝试另一种可能性。尽管可以考虑使用动态规划或广度优先搜索等其他算法，但由于解决这个问题需要生成所有可能的序列而不仅仅是计算数量，回溯法因其能够自然地处理这种'生成与测试'的需求而更为适合。
🦆
在回溯过程中，如何保证每个节点在它的所有子孙节点之前出现在序列中？
▷
在回溯过程中，每次从队列中选取一个节点作为序列中的下一个节点时，该节点的所有子节点都会被添加到队列中。这确保了在该节点后面的任何选择都只能从这些子节点或者其他已经在队列中的节点中进行选择。由于我们只从队列中移除已经添加到路径中的节点，并将其子节点加入队列，这样设计自然保证了每个节点必须在它的所有子孙节点之前被处理和添加到序列中，符合二叉搜索树的构建规则。
🦆
在算法中，你提到了使用队列来维护当前可插入的节点，为什么选择使用队列而不是其他数据结构如栈或优先队列？
▷
在本算法中，使用队列而不是栈或优先队列的主要原因是队列能够更自然地模拟广度优先的节点处理顺序，这对于本问题是理想的。队列允许我们以几乎与宽度优先搜索（BFS）相似的方式处理节点，但与传统的BFS不同，此处的队列在每次迭代中可能会根据节点的子节点动态变化。使用栈会导致我们以深度优先的顺序处理节点，这不符合题目要求的可能序列生成逻辑。优先队列（基于某种优先级排序的队列）在这里也不适用，因为节点的处理顺序仅由它们在树中的父子关系决定，而不是某种独立的优先级度量。

相关问题

求和路径迷路的机器人