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

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

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

[3,9,20,15,7]

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

Soluition 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 int[] levelOrder(TreeNode root) {
        if (root == null)
            return new int[0];
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        LinkedList<Integer> buffer = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            buffer.add(node.val);
            if (node.left != null)
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
        }
        int[] result = new int[buffer.size()];
        for (int i = 0; i < result.length; i++)
            result[i] = buffer.get(i);
        return result;
    }
}

Solution 2

cpp

#include <vector>
using std::vector;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
    vector<int> result;
    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)
        {
            for (size_t i = 0; i < list_cur.size(); i++)
            {
                TreeNode *node = list_cur[i];
                if (node == NULL)
                    continue;
                result.push_back(node->val);
                list_next.push_back(node->left);
                list_next.push_back(node->right);
            }
            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;
    }
};