[leetcode]102. Binary Tree Level Order Traversal@Java解题报告

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

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] ]

package go.jacob.day806; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; /** * 102. Binary Tree Level Order Traversal * * @author Jacob * */ public class Demo1 { /* * 推荐解法 */ public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if (root == null) return res; //层序遍历需要用到队列 Queue<TreeNode> queue = new LinkedList<TreeNode>(); //推荐用offer代替add queue.offer(root); while(!queue.isEmpty()){ //用size控制循环次数 int size=queue.size(); List<Integer> list = new ArrayList<Integer>(); for(int i=0;i<size;i++){ TreeNode node=queue.poll(); list.add(node.val); if(node.left!=null) queue.offer(node.left); if(node.right!=null) queue.offer(node.right); } res.add(list); } return res; } /* * My Solution * 二叉树的层序遍历 * 唯一区别是：需要定义一个节点，记录每一行的最后一个节点 */ public List<List<Integer>> levelOrder_byme(TreeNode root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if (root == null) return res; //层序遍历需要用到队列 Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); //lastNodeOfLine为每一行最后一个节点 TreeNode lastNodeOfLine = root; //临时记录每一行的节点，当改行遍历结束，tmpLastNode即为lastNodeOfLine TreeNode tmpLastNode = null; while (!queue.isEmpty()) { TreeNode node = queue.poll(); List<Integer> list = new ArrayList<Integer>(); //如果当前node不是lastNodeOfLine，继续循环 while (node != lastNodeOfLine) { if (node.left != null) { tmpLastNode = node.left; queue.add(node.left); } if (node.right != null) { tmpLastNode = node.right; queue.add(node.right); } list.add(node.val); node = queue.poll(); } //当前node是改行最后一个节点 if (node.left != null) { tmpLastNode = node.left; queue.add(node.left); } if (node.right != null) { tmpLastNode = node.right; queue.add(node.right); } list.add(node.val); lastNodeOfLine = tmpLastNode; res.add(list); } return res; } private class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }