从上往下打印出二叉树的每个节点(思路和实现)

KLQ 2020-04-27 10:39:40 java常见问答 5791

你知道从上往下打印出二叉树的每个节点,同层节点从左至右打印的思路和代码实现方式吗?下面一起来了解一下吧!

题目:

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

思路1

代码实现:

/**
思路是用arraylist模拟一个队列来存储相应的TreeNode
*/
public class Solution
{
    public ArrayList < Integer > PrintFromTopToBottom(TreeNode root)
    {
        ArrayList < Integer > list = new ArrayList < > ();
        ArrayList < TreeNode > queue = new ArrayList < > ();
        if (root == null)
        {
            return list;
        }
        queue.add(root);
        while (queue.size() != 0)
        {
            TreeNode temp = queue.remove(0);
            if (temp.left != null)
            {
                queue.add(temp.left);
            }
            if (temp.right != null)
            {
                queue.add(temp.right);
            }
            list.add(temp.val);
        }
        return list;
    }
}

思路2:

一、将第一个元素加入队列

二、队列不为空时取队首元素

三、将下一层元素加入队尾

四、调到第二步,直到队列为空

代码实现:

/*
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> result;
        if(NULL == root)
            return result;
         
        queue
        <TreeNode* > q;
        q.push(root);
        while(!q.empty())
        {
            TreeNode* temp = q.front();
            q.pop();
            result.push_back(temp->val);
            if(NULL != temp->left)
                q.push(temp->left);
            if(NULL != temp->right)
                q.push(temp->right);
        }
        return result;
    }
};

思路3:

借助队列实现

代码实现:

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

以上就是和从上往下打印二叉树相关的实例内容了,你都了解了吗?更多的java实例,请继续来奇Q工具网了解吧。