剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如: 给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

提示：

节点总数 <= 1000

注意：本题与主站 102 题相同：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

利用队列进行遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)
            return new ArrayList<List<Integer>>();
        Queue<TreeNode> mainQueue = new LinkedList<TreeNode>();
        Queue<TreeNode> subQueue = new LinkedList<TreeNode>();
        Queue<TreeNode> emptyQueueTemp;
        LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();
        LinkedList<Integer> buffer;
        mainQueue.offer(root);
        while (!mainQueue.isEmpty()) {
            buffer = new LinkedList<>();
            while (!mainQueue.isEmpty()) {
                TreeNode node = mainQueue.poll();
                buffer.add(node.val);
                if (node.left != null)
                    subQueue.offer(node.left);
                if (node.right != null)
                    subQueue.offer(node.right);
            }
            emptyQueueTemp = mainQueue;
            mainQueue = subQueue;
            subQueue = emptyQueueTemp;
            result.add(buffer);
        }
        return result;
    }
}

Solution 2

cpp

class Solution
{
public:
    vector<vector<int>> result;
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<TreeNode *> list_cur;
        vector<TreeNode *> list_next;
        result.clear();

        list_cur.push_back(root);
        while (list_cur.size() != 0 || list_next.size() != 0)
        {
            vector<int> layer;
            for (size_t i = 0; i < list_cur.size(); i++)
            {
                TreeNode *node = list_cur[i];
                if (node == NULL)
                    continue;
                layer.push_back(node->val);
                list_next.push_back(node->left);
                list_next.push_back(node->right);
            }
            if (layer.size() != 0)
                result.emplace_back(layer);
            list_cur.clear();
            for (size_t i = 0; i < list_next.size(); i++)
                list_cur.push_back(list_next[i]);
            list_next.clear();
        }
        return result;
    }
};