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]
]
/**
* 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) {
vector<vector<int>> res;
vector<int> one_res; TreeNode* p = root;
TreeNode* first = NULL; queue<TreeNode*> que;
if(p) que.push(p); while(!que.empty()){
p = que.front();
que.pop(); if(first == p){//碰到每层的第一个时就把上一层次的所有结点加入结果集
res.push_back(one_res);
one_res.clear();
first = NULL;
} one_res.push_back(p->val); if(first==NULL && p->left!=NULL){
first = p->left;
}
if(first==NULL && p->right!=NULL){
first = p->right;
} if(p->left){
que.push(p->left);
}
if(p->right){
que.push(p->right);
}
} if(!one_res.empty()){
res.push_back(one_res);
}
return res;
}
};
Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7}
,
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
/**
* 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 {
private:
void levelOrderBottom(TreeNode* root,vector<vector<int>>& res,int depth){
if(!root) return;
if(depth==res.size()){
res.push_back({});
}
res[depth].push_back(root->val);
levelOrderBottom(root->left,res,depth+);
levelOrderBottom(root->right,res,depth+);
}
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
levelOrderBottom(root,res,);
reverse(res.begin(),res.end());
return res;
}
};
2.先求高度,无需反转,4ms
/**
* 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 {
private:
int getTreeHeith(TreeNode* root){
if(!root) return ;
return max(getTreeHeith(root->left) ,getTreeHeith(root->right)) + ;
}
void levelOrderBottom(TreeNode* root,vector<vector<int>>& res,int depth){
if(!root) return;
res[depth].push_back(root->val);
levelOrderBottom(root->left,res,depth-);
levelOrderBottom(root->right,res,depth-);
}
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
int dep = getTreeHeith(root);
vector<vector<int>> res(dep,vector<int>());
levelOrderBottom(root,res,dep-);
return res;
}
};
Binary Tree Level Order Traversal,Binary Tree Level Order Traversal II的更多相关文章
-
35. Binary Tree Level Order Traversal &;&; Binary Tree Level Order Traversal II
Binary Tree Level Order Traversal OJ: https://oj.leetcode.com/problems/binary-tree-level-order-trave ...
-
LeetCode: Binary Tree Level Order Traversal &;&; Binary Tree Zigzag Level Order Traversal
Title: Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to ...
-
【LeetCode】105 &; 106 Construct Binary Tree from (Preorder and Inorder) || (Inorder and Postorder)Traversal
Description: Given arrays recording 'Preorder and Inorder' Traversal (Problem 105) or 'Inorder and ...
-
LEETCODE —— binary tree [Same Tree] &;&; [Maximum Depth of Binary Tree]
Same Tree Given two binary trees, write a function to check if they are equal or not. Two binary tre ...
-
遍历二叉树 traversing binary tree 线索二叉树 threaded binary tree 线索链表 线索化
遍历二叉树 traversing binary tree 线索二叉树 threaded binary tree 线索链表 线索化 1. 二叉树3个基本单元组成:根节点.左子树.右子树 以L.D.R ...
-
Week2 - 669. Trim a Binary Search Tree &; 617. Merge Two Binary Trees
Week2 - 669. Trim a Binary Search Tree & 617. Merge Two Binary Trees 669.Trim a Binary Search Tr ...
-
HDU 3999 The order of a Tree
The order of a Tree Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe ...
-
hdu3999The order of a Tree (二叉平衡树(AVL))
Problem Description As we know,the shape of a binary search tree is greatly related to the order of ...
-
<;hdu - 3999>; The order of a Tree 水题 之 二叉搜索的数的先序输出
这里是杭电hdu上的链接:http://acm.hdu.edu.cn/showproblem.php?pid=3999 Problem Description: As we know,the sha ...
随机推荐
-
python 使用pymssql连接sql server数据库
python 使用pymssql连接sql server数据库 #coding=utf-8 #!/usr/bin/env python#------------------------------ ...
-
kubernetes听云实战发布版
➠更多技术干货请戳:听云博客 听云线上使用k8s已经有一段时间了,下面对一些听云使用过程中的问题进行一些梳理,包括架构设计,安装部署和后期维护. 目录结构如下: 下面进入正题: 我们以听云系统的一个报 ...
-
verilog中=和<;=的区别
一般情况下使用<=,组合逻辑使用=赋值,时序逻辑使用<=赋值: 举个例子:初始化m=1,n=2,p=3:分别执行以下语句 1.begin m=n:n=p:p=m: end 2.begin ...
-
qt中的udp编程
UDP QUdpSocket ---> upd socket 1.创建 QUdpSocket *p = new QUdpSocket(); 2.最先接收数据一方 调用bind-> ip/p ...
-
Eclipse安装Gradle插件
1.window下安装Gradle见https://www.cnblogs.com/felixzh/p/9203271.html2.eclipse中依次打开help>Install new so ...
-
Bootstrap框架介绍
Bootstrap框架介绍 一.Bootstarp环境部署 1>.什么是Bootstartp框架 Bootstrap是Twitter开源的基于HTML.CSS.JavaScript的前端框架.它 ...
-
Java基础84 javaBean规范
1.javaBean的概述 1.javaBeam(咖啡豆)是一种开发规范,也可以说是一种技术. 2.JavaBean就是一个普通java类,只要符合以下规定才能称作为javaBean: ...
-
Python基础教程-Dict和Set
Python的dict Python内置了字典:dict全称dictionary,在其他语言中也称为map,使用键-值(key-value)存储,具有极快的查找速度. 比如,要根据同学的名字查找对应的 ...
-
架构师必须知道的26项PHP安全实践
PHP是一种开源服务器端脚本语言,应用很广泛.Apache web服务器提供了这种便利:通过HTTP或HTTPS协议,访问文件和内容.配置不当的服务器端脚本语言会带来各种各样的问题.所以,使用php时 ...
-
(转)Django常用命令
转自GoodSpeed,http://www.cnblogs.com/cacique/archive/2012/09/30/2709145.html . . . . .