二叉樹相關(guān)問題解題套路
- 廣度優(yōu)先遍歷（BFS：Breath First Search）优训、深度優(yōu)先遍歷（DFS：Depth First Search）早敬，廣度優(yōu)先（按層）遍歷用隊(duì)列荷愕，深度優(yōu)先遍歷優(yōu)先用遞歸荐类，棧的實(shí)現(xiàn)要比遞歸復(fù)雜一些。
注意點(diǎn)
- 換行打印需要兩個(gè)指針：一個(gè)保存當(dāng)前行的最右節(jié)點(diǎn)琅束，一個(gè)跟蹤下一行最新加入的節(jié)點(diǎn)葵腹，當(dāng)當(dāng)前行最右節(jié)點(diǎn)彈出時(shí)，更新為下一行最新加入的節(jié)點(diǎn)，這一行便可以跟下一行的節(jié)點(diǎn)區(qū)分開來。
- 之字形打印鏈表需要三個(gè)指針不脯，一個(gè)保存當(dāng)前行在隊(duì)列中最后彈出的節(jié)點(diǎn)冲簿，一個(gè)保存向右遍歷時(shí)上一行的最右節(jié)點(diǎn)彤断，一個(gè)保存向左遍歷時(shí)上一行的
最左節(jié)點(diǎn)。奇數(shù)行隊(duì)列彈出隊(duì)頭闸衫，往隊(duì)尾添加新節(jié)點(diǎn)，先添加左子節(jié)點(diǎn)睛琳，后添加右子節(jié)點(diǎn)募闲；偶數(shù)行隊(duì)列彈出隊(duì)尾农渊，往隊(duì)頭添加新節(jié)點(diǎn)沼溜，先添加右子節(jié)點(diǎn)，后添加左子節(jié)點(diǎn)鞍帝。
目錄
- 從上往下打印二叉樹
- 把二叉樹打印成多行
- 按之字形順序打印二叉樹（較難床绪，還需要練習(xí)）
- 序列化二叉樹（不能做到bug free绩社，還需練習(xí)）
從上往下打印二叉樹
從上往下打印出二叉樹的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode p = queue.poll();
res.add(p.val);
if (p.left != null) {
queue.add(p.left);
}
if (p.right != null) {
queue.add(p.right);
}
}
return res;
}
把二叉樹打印成多行
從上到下按層打印二叉樹疾渴，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行店量。
- 二叉樹按層打印，必然是用隊(duì)列實(shí)現(xiàn)
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
if (pRoot == null) {
res.add(list);
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
// last 存放當(dāng)前行最右節(jié)點(diǎn)，nlast保存最新加入隊(duì)列的節(jié)點(diǎn)
TreeNode last = pRoot, nlast = pRoot;
while (!queue.isEmpty()) {
TreeNode p = queue.poll();
list.add(p);
if (p.left != null) {
queue.add(p.left);
nlast = p.left;
}
if (p.right != null) {
queue.add(p.right);
nlast = p.right;
}
// 當(dāng)隊(duì)列彈出的節(jié)點(diǎn)跟last節(jié)點(diǎn)相同署惯，說明這一行打印完了
// last更新為nlast，也就是下一行的最右節(jié)點(diǎn)
if (p == last) {
last = nlast;
res.add(list);
list = new ArrayList<>();
}
}
return res;
}
按之字形順序打印二叉樹
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印黄选，第二層按照從右至左的順序打印貌夕，第三行按照從左到右的順序打印啡专，其他行以此類推们童。
- 雙向鏈表鲸鹦，奇數(shù)層往隊(duì)尾添加元素，彈出隊(duì)頭齐板；偶數(shù)層往隊(duì)頭添加元素甘磨，彈出隊(duì)尾。left監(jiān)視偶數(shù)層是否到達(dá)最左邊庵朝，right監(jiān)視奇數(shù)層是否到達(dá)最右邊
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>();
if (pRoot == null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList();
queue.add(pRoot);
boolean leftToRight = true;
TreeNode left = pRoot, right = pRoot;
while (!queue.isEmpty()) {
if (leftToRight) {
TreeNode p = queue.poll();
list.add(p.val);
if (p.left != null) {
queue.add(p.left);
}
if (p.right != null) {
queue.add(p.right);
}
if (p == right) {
left = queue.peek();
res.add(list);
list = new ArrayList<>();
}
} else {
TreeNode p = queue.pollLast();
list.add(p.val);
if (p.right != null) {
queue.addFirst(p.right);
}
if (p.left != null) {
queue.addFirst(p.left);
}
if (p == left) {
right = queue.peekLast();
res.add(list);
list = new ArrayList<>();
}
}
leftToRight = !leftToRight;
}
return res;
}
序列化二叉樹
請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來序列化和反序列化二叉樹
- 序列化和反序列化過程如果用遞歸實(shí)現(xiàn)肺蔚，對(duì)于每一個(gè)節(jié)點(diǎn)都需要不斷地將StringBuilder做toString過程宣羊，最終其實(shí)是每個(gè)字符串單獨(dú)相連接的過程，這個(gè)效率是很低的族操。所以我們選用隊(duì)列實(shí)現(xiàn)
String Serialize(TreeNode root) {
if (root == null) {
return "[]";
}
StringBuilder sb = new StringBuilder();
LinkedList<TreeNode> q = new LinkedList<>();
q.add(root);
sb.append("[").append(root.val).append(",");
while (!q.isEmpty()) {
TreeNode p = q.poll();
if (p.left != null) {
sb.append(p.left.val).append(",");
q.add(p.left);
} else {
sb.append("#,");
}
if (p.right != null) {
sb.append(p.right.val).append(",");
q.add(p.right);
} else {
sb.append("#,");
}
}
return sb.deleteCharAt(sb.length() - 1).append("]").toString();
}
TreeNode Deserialize(String str) {
if (str == null || str.equals("[]")) {
return null;
}
String[] arr = str.substring(1, str.length() - 1).split(",");
int k = 0, len = arr.length;
LinkedList<TreeNode> q = new LinkedList<>();
TreeNode root = new TreeNode(Integer.valueOf(arr[k++]));
q.add(root);
while (k < len && !q.isEmpty()) {
TreeNode p = q.poll();
if (k < len && !"#".equals(arr[k])) {
p.left = new TreeNode(Integer.valueOf(arr[k]));
q.add(p.left);
}
k++;
if (k < len && !"#".equals(arr[k])) {
p.right = new TreeNode(Integer.valueOf(arr[k]));
q.add(p.right);
}
k++;
}
return root;
}
