JZ22 — 从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

题目分析

二叉树的层次遍历。
使用队列来实现就OK了，策略如下：
1. 取队头结点
2. 将左右子结点添加进队列（先判断子结点是否为NULL）
3. 输出头结点的值
4. 将头结点删除

一直循环到队列为空即可。

C++

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution
{
public:
    vector<int> PrintFromTopToBottom(TreeNode *root)
    {
        vector<int> ans;
        if (!root)
            return ans;
        TreeNode *p;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty())
        {
            p = q.front();
            q.pop();
            if (p->left)
                q.push(p->left);
            if (p->right)
                q.push(p->right);
            ans.push_back(p->val);
        }
        return ans;
    }
};

Java

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 {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null)
            return ans;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            ans.add(q.peek().val);
            if (q.peek().left != null)
                q.add(q.peek().left);
            if (q.peek().right != null)
                q.add(q.peek().right);
            q.poll();
        }
        return ans;
    }
}