題目描述
請實作一個函式按照之字形列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右至左的順序列印，第三行按照從左到右的順序列印，其他行以此類推，
思路
層序遍歷二叉樹， 遍歷到奇數行時，使用尾插法將資料插入鏈表， 遍歷到偶數行時，使用頭插法將資料插入鏈表，時間復雜度O(n)，空間復雜度O(n)，
代碼
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
if(pRoot == null) {
return lists;
}
LinkedList<TreeNode> q = new LinkedList<>();
q.add(pRoot);
boolean rev = false;
while(!q.isEmpty()) {
int size = q.size();
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < size; i++) {
TreeNode curr = q.poll();
if(curr.left != null) {
q.add(curr.left);
}
if(curr.right != null) {
q.add(curr.right);
}
if(rev) {
list.add(0, curr.val);
} else {
list.add(curr.val);
}
}
rev = !rev;
lists.add(list);
}
return lists;
}
}
筆記
掌握層序遍歷，LinkedList底層是雙向鏈表，簡單插入即可，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71893.html
標籤：其他
上一篇：堆-優先佇列[陣列]
下一篇：把二叉樹列印成多行