Java版LeetCode

Appearance

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

题目 ​

从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。

给定一个由不同节点 组成的二叉搜索树 root，输出所有可能生成此树的数组。

示例 1:

输入: root = [2,1,3]
输出: [[2,1,3],[2,3,1]]
解释: 数组 [2,1,3]、[2,3,1] 均可以通过从左向右遍历元素插入树中形成以下二叉搜索树
       2 
      / \ 
     1   3
输入: root = [2,1,3]
输出: [[2,1,3],[2,3,1]]
解释: 数组 [2,1,3]、[2,3,1] 均可以通过从左向右遍历元素插入树中形成以下二叉搜索树
       2 
      / \ 
     1   3

示例 2:

输入: root = [4,1,null,null,3,2]
输出: [[4,1,3,2]]
输入: root = [4,1,null,null,3,2]
输出: [[4,1,3,2]]

提示：

  • 二叉搜索树中的节点数在 [0, 1000] 的范围内
  • 1 <= 节点值 <= 10^6
  • 用例保证符合要求的数组数量不超过 5000

题解 ​

java
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;
}
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;
}