Levelorder Traversal

层级遍历有两种，一种是双队列辅助，一种是单队列

• Two queues

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        cur, nxt = collections.deque([root]), collections.deque([])
        res, tmp = [], []

        while cur:
            node = cur.pop()
            tmp.append(node.val)
            if node.left:
                nxt.appendleft(node.left)
            if node.right:
                nxt.appendleft(node.right)
            if not cur:
                cur, nxt = nxt, cur
                res.append(tmp)
                tmp = []

        return res

Java版本

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        Queue<TreeNode> cur = new LinkedList<>();
        Queue<TreeNode> nxt = new LinkedList<>();
        List<Integer> tmp = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        cur.add(root);

        while (!cur.isEmpty()) {
            TreeNode node = cur.remove();
            tmp.add(node.val);
            if (node.left != null) {
                nxt.add(node.left);
            }
            if (node.right != null) {
                nxt.add(node.right);
            }
            if (cur.isEmpty()) {
                result.add(new ArrayList<>(tmp));
                tmp.clear();
                cur = nxt;
                nxt = new LinkedList<TreeNode>();
            }
        }

        return result;
    }
}

• One queue

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        q, cur, nxt = collections.deque([root]), 1, 0
        res, tmp = [], []

        while q:
            node = q.pop()
            tmp.append(node.val)
            cur -= 1
            if node.left:
                q.appendleft(node.left)
                nxt += 1
            if node.right:
                q.appendleft(node.right)
                nxt += 1
            if not cur:
                cur, nxt = nxt, cur
                res.append(tmp)
                tmp = []

        return res

Java版本

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        Queue<TreeNode> queue = new LinkedList<>();
        int cur = 1;
        int nxt = 0;
        List<Integer> tmp = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.remove();
            cur--;
            tmp.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
                nxt++;
            }
            if (node.right != null) {
                queue.add(node.right);
                nxt++;
            }
            if (cur == 0) {
                result.add(new ArrayList<>(tmp));
                tmp.clear();
                cur = nxt;
                nxt = 0;
            }
        }

        return result;
    }
}