層序周遊:從根節點開始,從上到下,從左到右通路每一個節點。
二叉樹節點定義:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
層序周遊:用隊列實作。
具體操作:根節點入隊;while循環判斷隊列不空時,彈出一個節點,通路它,并把它的左右孩子節點入隊(父親節點出隊,兒子節點入隊)。有點花木蘭代父從軍的意思哈。
最簡單的層序周遊模闆:
public void levelOrder(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.println(cur.val);
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
解答LeetCode102、107、103、199題,隻需要在上面的模闆進行修改。
102. Binary Tree Level Order Traversal
題目位址:https://leetcode.com/problems/binary-tree-level-order-traversal/description/
根據題目要求我們需要知道周遊時的層數,也就是說,需要知道每層有多少個節點,而隊列的size()就是這個隊列裡面的節點數量,每次進入while循環的時候通過queue.size()就可以得到這一層的節點數,然後周遊這些節點就可以了。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<size;i++){
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
res.add(list);
}
return res;
}
}
107. Binary Tree Level Order Traversal II
題目位址:https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/
這一題的層是從下到上的,隻需要改變res.add(E e)方式,改為res.add(int index,E e);具體的這兩個方法有什麼不同可以參考Java的APIhttps://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/ArrayList.html
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null ){
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<size;i++){
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
res.add(0,list);
}
return res;
}
}
103. Binary Tree Zigzag Level Order Traversal
題目位址:https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/
“之”字型層序周遊,有了上面兩個題的基礎,這個題很好解決,隻需要記錄一下層數,分情況使用ArrayList.add(E e)和ArrayList.add(int index,E e)即可解決。
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null ){
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int level = 0;
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<size;i++){
TreeNode cur = queue.poll();
if(level %2 ==0){
list.add(cur.val);
}else{
list.add(0,cur.val);
}
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
res.add(list);
level++;
}
return res;
}
}
199. Binary Tree Right Side View
題目位址:https://leetcode.com/problems/binary-tree-right-side-view/description/
二叉樹的右視圖,層序周遊,隻将每層最後一個節點的值添加ArrayList中傳回。
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<size;i++){
TreeNode cur = queue.poll();
list.add(cur.val);
if(cur.left!=null){
queue.offer(cur.left);
}
if(cur.right!=null){
queue.offer(cur.right);
}
}
res.add(list.get(size-1));
}
return res;
}
}