当前位置:   article > 正文

从上到下打印二叉树(层序遍历法)_层序打印二叉树

层序打印二叉树

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

 

例如:

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

    3

   / \

  9 20

    / \

   15 7

 

返回:

[3,9,20,15,7]

 

提示:

节点总数 <= 1000

 

解题思路:

使用层序遍历二叉树并把值存入数组中再输出。(层序遍历需要用到队列)

 

算法流程:

1.创建vector容器result存储要打印的值

2.如果二叉树为空,直接返回result(此时为空)

3.创建队列q,并且把树的根结点入队

4.循环直到队列为空

               创建结点node存储队头元素

               删除队头元素

               如果node的左孩子存在

                       则入队

               如果node的右孩子存在

                       则入队

               把node存入result

5.返回result

 

代码:

class Solution {

public:

    vector<int> levelOrder(TreeNode* root) {

    vector<int> result;

    if(root==nullptr) return result;

    queue<TreeNode*> q;

    q.push(root);

    while(!q.empty()) {

        TreeNode* node=q.front();

        q.pop();

        if(node->left!=nullptr)

            q.push(node->left);

        if(node->right!=nullptr)

            q.push(node->right);

        result.push_back(node->val);

    }

    return result;

    }

};

 

运行步骤:

    3

   / \

  9 20

      / \

    15  7

 

3入队

node=3,3出队,9,20入队

result:[3]

node=9,9出队

result:[3 9]

node=20,20出队,15,7入队

result:[3 9 20]

node=15,15出队

result:[3 9 20 15]

node=7,7出队

result:[3 9 20 15 7]

返回result:[3 9 20 15 7]

 

 

 

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/837154
推荐阅读
相关标签
  

闽ICP备14008679号