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

相关文章

来自专栏机器学习与自然语言处理

二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历

  对于一种数据结构而言,遍历是常见操作。二叉树是一种基本的数据结构,是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下: 1 typedef str...

2906
来自专栏韦弦的偶尔分享

Swift 验证二叉搜索树- LeetCode

对isValidBSTUtil(node.left, min, node.val) && isValidBSTUtil(node.right, node.val...

1554
来自专栏编程之旅

数据结构——二叉查找树(C语言)

二叉查找树,也称作二叉搜索树,有序二叉树,排序二叉树,而当一棵空树或者具有下列性质的二叉树,就可以被定义为二叉查找树:

1294
来自专栏LeetCode

LeetCode 783 & 530 Distance Between BST Nodes

Given a Binary Search Tree (BST) with the root node root, return the minimum dif...

1390
来自专栏后端之路

优先级队列之PriorityQueue

背景 前面几篇的队列基本都是和插入顺序相关的,一般来说可以先进先出,当然也可以通过双向队列实现进后出等等 那么在开发中还存在如下一些需求 不同的任务过来可以进入...

3067
来自专栏mathor

线性表(一)

862
来自专栏Android知识点总结

Java总结之容器家族--Collection

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

1202
来自专栏个人分享

JAVA源码走读(一) HashMap与ArrayList

HashMap是基于哈希表的Map接口的实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变...

1002
来自专栏小灰灰

JDK容器学习之TreeMap (一) : 底层数据结构

TreeMap 在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择 Linke...

2309
来自专栏LeetCode

LeetCode 114. Flatten Binary Tree to Linked List

关于二叉树的题目,最直接最简单的方法就是采用递归,因为二叉树具有天然的递归结构,实际上二叉树的定义就是用递归的思想来定义的:一个节点的左右子树任然是一个二叉树。

250

扫码关注云+社区