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,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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


我使用的是广搜,要用到队列。但由于是二叉树,可以时间效率更高的方法,dfs遍历,标记每个节点的顺序,1,2,3,4 空节点就跳过。在相应顺序为下标中的数组中插入相应的值。
然后1  , 2 3 ,4 5 6 7 8 ,...按照这个规律插到二维数组中。


c++ 广搜
lass Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        
       queue<TreeNode*> q;
       queue<int> q2;
       vector<vector<int> > ans;
       if(root==NULL)
           return ans;
       q.push(root);q2.push(0);
       vector<int> res;
       int j=-1;
       while(!q.empty())
       {
           TreeNode* term = q.front();
           int i = q2.front();
           if(i==j+2)
           {
               ans.push_back(res);
               res.clear();
               j++;
           }
           res.push_back(term->val);     
           q.pop();q2.pop();
           if(term->left!=NULL)
           { q.push(term->left);q2.push(i+1);}
           if(term->right!=NULL)
           { q.push(term->right);q2.push(i+1);}
       }
       if(!res.empty())
           ans.push_back(res);
        
       return ans;      
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java成长之路

【天梯 - Wikioi】2235 机票打折

431
来自专栏数据结构与算法

洛谷P2759 奇怪的函数(log 二分)

471
来自专栏武培轩的专栏

快手2018春招后端笔试题解

计算(x^y)%N 题目描述 计算(x^y)%N 注:(x^y)表示x的y次方 输入描述: 每个测试用例一行 每行为空格隔开的 int64_t 类型,分别对应x...

3485
来自专栏Java3y

二叉树就这么简单

一、二叉树就是这么简单 本文撇开一些非常苦涩、难以理解的概念来讲讲二叉树,仅入门观看(或复习)…. 首先,我们来讲讲什么是树: 树是一种非线性的数据结构,相对于...

3888
来自专栏技术碎碎念

LeetCode-15-3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b ...

35111
来自专栏desperate633

LintCode 将二叉树拆成链表题目分析代码

将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说,用二叉树的 right 指针,来表示链表中的 next 指针。

543
来自专栏Bingo的深度学习杂货店

Q108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

3103
来自专栏King_3的技术专栏

leetcode-38-Count and Say

2277
来自专栏程序员互动联盟

【C++练手】C++实现单链表

前几天找实习的时候,一个面试官给我留了一个题,做一个链表demo,要求实现创建、插入、删除等操作。 链表是一种常见的数据结构,它是一种物理存储单元上非连续、非顺...

3287
来自专栏开源优测

屌爆了,一句话描述各种编程语言

Python: What if everything was a dict? Java: What if everything was an object? J...

34710

扫码关注云+社区