二叉树的层次遍历
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
//层序遍历,保存右边的
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
if(i == size - 1){
res.add(node.val);
}
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
}
return res;
}
}
优化: 每层右孩子先入队。
if(node.right != null){
queue.offer(node.right);
}
if(node.left != null){
queue.offer(node.left);
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
//小优化:每层右孩子先入队。
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
if(i == 0){ //小优化:每层右孩子先入队
res.add(node.val);
}
if(node.right != null){
queue.offer(node.right);
}
if(node.left != null){
queue.offer(node.left);
}
}
}
return res;
}
}
时间上优化了一点点
429.N叉树的层序遍历
一样的,把左右孩子换成遍历数组即可
if(children != null){
for (Node child : children) {
if (child != null) {
que.offerLast(child);
}
}
}
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
//三个构造器
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> list = new ArrayList<>();
Deque<Node> que = new LinkedList<>();
if (root == null) {
return list;
}
que.offer(root);
while (!que.isEmpty()) {
int levelSize = que.size();
List<Integer> levelList = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
Node poll = que.pollFirst();
levelList.add(poll.val);
List<Node> children = poll.children;
if(children != null){
for (Node child : children) {
if (child != null) {
que.offerLast(child);
}
}
}
}
list.add(levelList);
}
return list;
}
}