C++实现LeetCode(102.二叉树层序遍历)

[LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
/ \
9  20
/  \
15   7

return its level order traversal as:

[
[3],
[9,20],
[15,7]
]

层序遍历二叉树是典型的广度优先搜索 BFS 的应用,但是这里稍微复杂一点的是,要把各个层的数分开,存到一个二维向量里面,大体思路还是基本相同的,建立一个 queue,然后先把根节点放进去,这时候找根节点的左右两个子节点,这时候去掉根节点,此时 queue 里的元素就是下一层的所有节点,用一个 for 循环遍历它们,然后存到一个一维向量里,遍历完之后再把这个一维向量存到二维向量里,以此类推,可以完成层序遍历,参见代码如下:

解法一:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            vector<int> oneLevel;
            for (int i = q.size(); i > 0; --i) {
                TreeNode *t = q.front(); q.pop();
                oneLevel.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            res.push_back(oneLevel);
        }
        return res;
    }
};

下面来看递归的写法,核心就在于需要一个二维数组,和一个变量 level,关于 level 的作用可以参见博主的另一篇博客 Binary Tree Level Order Traversal II 中的讲解,参见代码如下:

解法二:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        levelorder(root, 0, res);
        return res;
    }
    void levelorder(TreeNode* node, int level, vector<vector<int>>& res) {
        if (!node) return;
        if (res.size() == level) res.push_back({});
        res[level].push_back(node->val);
        if (node->left) levelorder(node->left, level + 1, res);
        if (node->right) levelorder(node->right, level + 1, res);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/102

类似题目:

Binary Tree Level Order Traversal II

Binary Tree Zigzag Level Order Traversal

Minimum Depth of Binary Tree

Binary Tree Vertical Order Traversal 

Average of Levels in Binary Tree

N-ary Tree Level Order Traversal

参考资料:

https://leetcode.com/problems/binary-tree-level-order-traversal/

https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/33445/Java-Solution-using-DFS

https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/33450/Java-solution-with-a-queue-used

https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/114449/A-general-approach-to-level-order-traversal-questions-in-Java

到此这篇关于C++实现LeetCode(102.二叉树层序遍历)的文章就介绍到这了,更多相关C++实现二叉树层序遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-21

C++实现LeetCode(100.判断相同树)

[LeetCode] 100. Same Tree 判断相同树 Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input:     1     

C++实现LeetCode(312.打气球游戏)

[LeetCode] 312. Burst Balloons 打气球游戏 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon iyou will get nums[left] * nums[i]

C++实现LeetCode(98.验证二叉搜索树)

[LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The ri

C++实现LeetCode(103.二叉树的之字形层序遍历)

[LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example

C++实现LeetCode(145.二叉树的后序遍历)

[LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历 Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3},    1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you d

C++实现LeetCode(139.拆分词句)

[LeetCode] 139. Word Break 拆分词句 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dic

C++实现LeetCode(97.交织相错的字符串)

[LeetCode] 97.Interleaving String 交织相错的字符串 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. Example 1: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Example 2: Input: s1 = &quo

C++实现LeetCode(99.复原二叉搜索树)

[LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树 Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,null,2]    1 / 3 \ 2 Output: [3,1,null,null,2]    3 / 1

C++实现LeetCode(107.二叉树层序遍历之二)

[LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二 Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Example 1: Input: root = [3

Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】

本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.

Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】

本文实例讲述了Python二叉树的遍历操作.分享给大家供大家参考,具体如下: # coding:utf-8 """ @ encoding: utf-8 @ author: lixiang @ email: lixiang_cn@foxmail.com @ python_version: 2 @ time: 2018/4/11 0:09 @ more_info: 二叉树是有限个元素的集合,该集合或者为空.或者有一个称为根节点(root)的元素及两个互不相交的.分别被称为左子树和

Java二叉树的遍历思想及核心代码实现

二叉树在计算机中的存储方式往往线性结构,线性存储分为顺序存储和链式存储,将二叉树按层序编号. 顺序结构:按编号的顺序进行存储,对于完全二叉树而言,顺序存储可以反映二叉树的逻辑,但是对于大多数的二叉树则无法反映其逻辑关系,不过可以用 ^ 来代替不存在的结点,但是如果这个树是一个右斜树,就非常浪费存储空间.所以二叉树的存储形式一般为链式存储结构. 链式存储:每一个结点都分有一个数据域(data)和两个指针域(lchild和rchild),指针域分别指向左孩子和右孩子,若为空则为null.遍历方式有四

层序遍历在ExtJs的TreePanel中的应用

原理非常简单,就是树的层序遍历,在遍历过程中遇到第一个叶子节点即完成工作. 效果如下图:代码如下: 复制代码 代码如下: var currentRootNode = null;//当前选择的根节点 function NodeClass() { //定义一个节点类 var nodeValue = null; var nextNode = null;//下一个节点 } function InitQueue(queue) { //初始化一个队列 queue = new NodeClass();//头节

JavaScript数据结构之二叉树的遍历算法示例

本文实例讲述了JavaScript数据结构之二叉树的遍历算法.分享给大家供大家参考,具体如下: 三种遍历的代码: function inOrder(node){//中序遍历 if(node!=null){ inOrder(node.left); document.write(node.show()+" "); inOrder(node.right); } } function preOrder(node){//先序遍历 if(node!=null){ document.write(no

C语言数据结构之线索二叉树及其遍历

C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,¥不能直接得到节点在遍历中的前驱和后继¥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

二叉树的遍历算法(详细示例分析)

复制代码 代码如下: #include<iostream>#include<assert.h>#include<stack>#include<queue>using namespace std;struct Node{    int v;    Node *leftChild,*rightChild;    Node():leftChild(NULL),rightChild(NULL){}    Node(int vv):leftChild(NULL),ri

PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依

python实现二叉树的遍历

本文实例为大家分享了python实现二叉树的遍历具体代码,供大家参考,具体内容如下 代码: # -*- coding: gb2312 -*- class Queue(object): def __init__(self): self.q = [] def enqueue(self, item): self.q.append(item) def dequeue(self): # if self.q != []: if len(self.q)>0: return self.q.pop(0) else

python3实现二叉树的遍历与递归算法解析(小结)

1.二叉树的三种遍历方式 二叉树有三种遍历方式:先序遍历,中序遍历,后续遍历 即:先中后指的是访问根节点的顺序 eg:先序 根左右 中序 左根右 后序 左右根 遍历总体思路:将树分成最小的子树,然后按照顺序输出 1.1 先序遍历 a 先访问根节点 b 访问左节点 c 访问右节点 a(b ( d ( h ) )( e ( i ) ))( c ( f )( g )) -- abdheicfg 1.2 中序遍历 a 先访问左节点 b 访问根节点 c 访问右节点 ( ( ( h ) d ) b ( (