二叉树的层序遍历「变题」

102. 二叉树的层序遍历

关于 DFS 实现二叉树的层序遍历更多内容可见 二叉树关于行的相关操作技巧

下面给出两种写法：BFS、DFS

// BFS
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            list.add(cur.val);
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        ans.add(list);
    }
    return ans;
}

// DFS
private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
    f(root, 0);
    return ans;
}
private void f(TreeNode root, int depth) {
    if (root == null) return ;
    if (ans.size() - 1 < depth) {
        List<Integer> list = new ArrayList<>();
        list.add(root.val);
        ans.add(list);
    } else {
        ans.get(depth).add(root.val);
    }
    f(root.left, depth + 1);
    f(root.right, depth + 1);
}

变题一：二叉树的锯齿形层序遍历

题目详情可见 二叉树的锯齿形层序遍历

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;
    Queue<TreeNode> q = new LinkedList<>();
    int reverse = 0;
    q.offer(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            list.add(cur.val);
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        // 反转顺序
        if (reverse == 1) {
            int l = 0, r = list.size() - 1;
            while (l < r) {
                int t = list.get(l);
                list.set(l, list.get(r));
                list.set(r, t);
                l++; r--;
            }
        }
        ans.add(list);
        reverse ^= 1;
    }
    return ans;
}

变题二：N 叉树，3 层为周期反转

本题是 二叉树的锯齿形层序遍历 的升级版！！

x
// N 叉树
public class DTreeNode {
    public int value;
    public List<DTreeNode> children;

    public DTreeNode(int value) {
        this.value = value;
        children = new ArrayList<>();
    }
}
public class Test {
    // 构建 N 叉树
    public static DTreeNode bulid() {
        int idx = 1, step = 10;
        DTreeNode root = new DTreeNode(idx++);
        Queue<DTreeNode> q = new LinkedList<>();
        q.offer(root);
        while (step > 0) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                DTreeNode cur = q.poll();
                DTreeNode c1 = new DTreeNode(idx++);
                DTreeNode c2 = new DTreeNode(idx++);
                cur.children.add(c1);
                cur.children.add(c2);
                q.offer(c1);
                q.offer(c2);
                if (i < sz - 1) System.out.print(cur.value + "==");
                else System.out.print(cur.value);
            }
            System.out.println();
            step--;
        }
        return root;
    }
    // 遍历 N 叉树
    public static List<List<Integer>> traversal(DTreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Queue<DTreeNode> q = new LinkedList<>();
        q.offer(root);
        int cnt = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            List<Integer> sub = new ArrayList<>();
            for (int i = 0; i < sz; i++) {
                DTreeNode cur = q.poll();
                sub.add(cur.value);
                for (DTreeNode c : cur.children) {
                    q.offer(c);
                }
            }
            // 三层一反转
            if (cnt / 3 % 2 == 1) {
                for (int i = 0, j = sub.size() - 1; i < j; i++, j--) {
                    int t = sub.get(i);
                    sub.set(i, sub.get(j));
                    sub.set(j, t);
                }
            }
            cnt++;
            ans.add(sub);
        }
        return ans;
    }
    public static void main(String[] args) {
        DTreeNode root = bulid();
        List<List<Integer>> traversal = traversal(root);
        for (List<Integer> sub : traversal) {
            System.out.println(sub.toString());
        }
    }
}

变题三：二叉树的右视图

题目详情可见 二叉树的右视图

xxxxxxxxxx
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            if (i == sz - 1) ans.add(cur.val);
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
    }
    return ans;
}