美文网首页
Leetcode102二叉树的层次遍历

Leetcode102二叉树的层次遍历

作者: answerLDA | 来源:发表于2019-11-03 13:50 被阅读0次

题目

给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]

代码及分析

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        //用来装返回结果
        vector<vector<int>> res;
        //用来装每一层的结果
        vector<int> cell;
        //用来装每一个被遍历的节点
        vector<TreeNode*> list;
        //先把根节点放进去
        list.push_back(root);
        //nextNum是下一层的元素个数;nextCell是下一层的开始位置。
        int nextNum=0,nextCell=1;
        //遍历列表
        for(int i = 0;i<list.size();i++){
            TreeNode* p = list[i];
            //如果到了这一层的开始位置,就把上一层的结果放进res里面,
            //临时遍历重新清零,并更新下一层的开始位置
            if(i==nextCell){
                res.push_back(cell);
                cell = {};
                nextCell += nextNum;
                nextNum=0;
            }
            //把这一层的元素放进临时层列表
            cell.push_back(p->val);
            //把左右的元素放进去待遍历列表中,并对下一层元素个数进行计数
            if(p->left){
                list.push_back(p->left);
                nextNum++;
            }
             if(p->right){
                list.push_back(p->right);
                 nextNum++;
            }
        }
        //把最后一层放进去结果里面
        res.push_back(cell);
        return res;
    }
};

相关文章

  • 二叉树的蛇形层次遍历(LeetCode.103)

    题目 解析 首先参考二叉树的层次遍历层次遍历二叉树(LeetCode--102二叉树的层次遍历)[https://...

  • 二叉树遍历

    二叉树遍历(非递归写法) 先序遍历 中序遍历 后序遍历 层次遍历 给定一个二叉树,返回其按层次遍历的节点值。 (即...

  • 二叉树的基本算法

    一、二叉树的递归遍历 二、二叉树的层次遍历 二叉树的层次遍历是指二叉树从上到下,从左到右遍历数据。同一层中的节点访...

  • Leetcode102二叉树的层次遍历

    题目 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如:给定二叉树: [3,...

  • 二叉树的层次遍历

    三道层次遍历题,同一个模板,这边用到的是两个队列 二叉树的层次遍历 LeetCode题目地址 二叉树的层次遍历 加...

  • 二叉树的层次遍历

    一、二叉树的层次遍历原理 如图所示为二叉树的层次遍历,即按照箭头所指方向,按照1、2、3、4的层次顺序,对二叉树中...

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 数据结构重学日记(二十二)二叉树的层次遍历

    二叉树的层次遍历也属于非递归遍历,和之前先序、中序、后序遍历的区别在于层次遍历需要借助队列来实现。 层次遍历的操作...

  • 二叉树遍历

    1.层次遍历(广度优先遍历) 用队列实现,队首出队,队首的子节点入队。 1,二叉树的层次遍历, 打印 2,二叉树的...

  • 力扣题解(树)

    100. 相同的树 101. 对称二叉树 102. 二叉树的层次遍历 103. 二叉树的锯齿形层次遍历 104. ...

网友评论

      本文标题:Leetcode102二叉树的层次遍历

      本文链接:https://www.haomeiwen.com/subject/lfbkbctx.html