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 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

基因名变化太快,比如PAM50

当然准备把这些基因跟ensembl数据库的ID对应的时候我发现少了3个,然后我搜索发现它们的symbol其实被修改了,可以说变化比较快啦,才几年时间,3 of ...

1022
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2818
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2152
来自专栏转载gongluck的CSDN博客

第17章 ioctl操作

#include <sys/ioctl.h> int ioctl(int fd, unsigned long request, ...); /usr/src/...

2989
来自专栏c#开发者

Clean up your BizTalk databases

Here are a few scripts / stored procedures that most of the Biztalk newbies woul...

3434
来自专栏成长道路

org.apache.spark.sql.AnalysisException: Table or view not found: `traintext`.`train`; line 1 pos 14;

恭喜老铁,跟我遇到了一样的问题,接下来是解决方法: 遇到的问题: org.apache.spark.sql.AnalysisException: Table o...

9220
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2159
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3719
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

761
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1142

扫码关注云+社区