二叉搜索树序列

题目链接

二叉搜索树序列

题目描述

注意点

• 二叉搜索树中的节点数在 [0, 1000] 的范围内
• 1 <= 节点值 <= 10^6

解答思路

• 本题的题目解释成一句话也就是：每一个节点都必须排在其子孙节点的前面，同一层的节点可以任意排列
• 首先想到的是广度优先遍历，将每一层的节点加入到一个List中，同一层的n个节点可以随意排列，有(n + 1) * n / 2种排列方式，当选出n个节点中某个节点i加入路径时，还需要将其左右节点加入到List末尾，左右节点可以排在同一层其他节点前面，但必须在根节点i后面。因为要寻找所有可能的序列，在选出某个节点作为路径后，还要考虑其他节点作为路径的情况，所以要进行回溯，需要将该节点从路径中移除，并且将List还原

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> BSTSequences(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        List<TreeNode> list = new ArrayList<>();
        if (root != null) {
            list.add(root);
        }
        List<Integer> sonRes = new ArrayList<>();
        bfs(res, sonRes, list);
        return res;
    }

    public void bfs(List<List<Integer>> res, List<Integer> sonRes, List<TreeNode> list) {
        // 队列为空，说明树已遍历完
        if (list.isEmpty()) {
            res.add(new ArrayList<>(sonRes));
            return;
        }
        int n = list.size();
        List<TreeNode> copy = new ArrayList<>(list);
        for (int i = 0; i < n; i++) {
            TreeNode node = list.get(i);
            sonRes.add(node.val);
            list.remove(i);
            if (node.left != null) {
                list.add(node.left);
            }
            if (node.right != null) {
                list.add(node.right);
            }
            bfs(res, sonRes, list);
            // 回溯
            sonRes.remove(sonRes.size() - 1);
            list = new ArrayList<>(copy);
        }
    }
}

关键点

• 理解题意
• 回溯的思想，不仅要将节点从路径中移除，还要将List还原，才能找到所有的路径，同时防止子孙节点出现在根节点前面