题解 | #求二叉树的层序遍历# 双 Queue

NC15求二叉树的层序遍历

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if(root == null) return new ArrayList<>();
        // write code here
        Queue<TreeNode> q1 = new ArrayDeque<>();
        Queue<TreeNode> q2 = new ArrayDeque<>();
        q1.add(root);
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        while (!q1.isEmpty() || !q2.isEmpty()) {
            ArrayList<Integer> arr = new ArrayList<>();
            if (!q1.isEmpty()) {
                while (!q1.isEmpty()) {
                    TreeNode t = q1.poll();
                    arr.add(t.val);
                    if (t.left != null) q2.add(t.left);
                    if (t.right != null) q2.add(t.right);
                }
            } else if (!q2.isEmpty()) {
                while (!q2.isEmpty()) {
                    TreeNode t = q2.poll();
                    arr.add(t.val);
                    if (t.left != null) q1.add(t.left);
                    if (t.right != null) q1.add(t.right);
                }
            }
            result.add(arr);

        }
        return result;
    }
}

在时间复杂度上并没有什么优势，但是非常容易理解，两个队列，轮流上阵，一个弹出时，另一个记录。