面试题 04.09. 二叉搜索树序列

题目

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

示例：
给定如下二叉树

graph TB
2((2)) --- 1((1))
2 --- 3((3))

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

题解

public List<List<Integer>> BSTSequences(TreeNode root) {
    if (root == null) {
        return new ArrayList<>(Collections.singleton(new ArrayList<>()));
    }

    List<List<Integer>> result = new ArrayList<>();

    BiConsumer<List<TreeNode>, Stack<Integer>> dfs = new BiConsumer<List<TreeNode>, Stack<Integer>>() {
        @Override
        public void accept(List<TreeNode> list, Stack<Integer> solution) {
            if (list.isEmpty()) {
                result.add(new ArrayList<>(solution));
                return;
            }

            for (int i = 0; i < list.size(); i++) {
                List<TreeNode> next = new ArrayList<>(list);
                TreeNode node = next.remove(i);
                solution.push(node.val);
                // 添加左右节点
                Optional.ofNullable(node.left).ifPresent(next::add);
                Optional.ofNullable(node.right).ifPresent(next::add);
                // dfs
                this.accept(next, solution);
                // 回溯
                solution.pop();
            }
        }
    };

    dfs.accept(new ArrayList<>(Collections.singletonList(root)), new Stack<>());

    return result;
}