力扣打卡:107. 二叉樹的層序遍歷 II
解題思路
正常的層序遍歷,最后進行交換即可
層序遍歷借助的資料結構是:佇列
-
首先將root節點加入佇列,然后記錄此時的長度,因為佇列的先進先出,所以需要有一個
len記錄每一層的數量\ -
同一層的遍歷通過
for來進行,每一次的遍歷都判斷此時的節點是否還有子節點,如果有加入到佇列中 -
因為len記錄了同一層的個數,所以每一次的遍歷,即使有上一層的節點和下一層的節點同時存在,但是也不會影響正確性
代碼
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
// 還是借助佇列,將二叉樹的順序輸出,然后交換位置即可
List<List<Integer>> ans = new ArrayList<>();
if(root==null) return ans;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int len = que.size();
List<Integer> list = new ArrayList<>();
for(int i=0; i<len; i++){
TreeNode t = que.poll();
list.add(t.val);
if(t.left!=null) que.offer(t.left);
if(t.right!=null) que.offer(t.right);
}
ans.add(list);
}
int left=0, right=ans.size()-1;
while(left < right){ // 不需要等于,因為left==right時,只剩下一個元素,不需要交換
List<Integer> temp = ans.get(left);
ans.set(left++,ans.get(right));
ans.set(right--,temp);
}
return ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342122.html
標籤：其他