姓名：譚旭東
學(xué)號(hào)：19011210016
一、基本概念
二叉樹有一般有三種遍歷方法：根據(jù)遍歷順序不同而區(qū)分
前序遍歷：根左右（第一次訪問節(jié)點(diǎn)，直接獲取值）
中序遍歷：左根右（第二次訪問節(jié)點(diǎn)時(shí)，也就是從該節(jié)點(diǎn)左子樹回來(lái)時(shí)，獲取該節(jié)點(diǎn)值）
后序遍歷：左右根（第三次訪問節(jié)點(diǎn)時(shí)，也就是從該節(jié)點(diǎn)右子樹回來(lái)時(shí)，獲取該節(jié)點(diǎn)值）
-
在遍歷過程中，我們?cè)L問節(jié)點(diǎn)的順序固定不變：根左右
- 但我們可以調(diào)整讀取節(jié)點(diǎn)值的時(shí)間，來(lái)達(dá)成我們想要的順序
- 注：二叉樹還有層序遍歷，一般使用類bfs的隊(duì)列方法來(lái)做
二、前序遍歷
1. 遞歸寫法
// 前序：遞歸方法遍歷
public List<Integer> preOrder1(TreeNode root) {
List<Integer> ans = new ArrayList<>();
preOrder_dfs(root, ans);
return ans;
}
public void preOrder_dfs(TreeNode node, List<Integer> ans) {
if (node == null)
return;
// 前序遍歷：首次進(jìn)入節(jié)點(diǎn)即獲取值
ans.add(node.val);
preOrder_dfs(node.left, ans);
preOrder_dfs(node.right, ans);
}
2. 非遞歸寫法
- 不使用遞歸的情況下，使用棧來(lái)保存各個(gè)節(jié)點(diǎn)
- 并且調(diào)整入棧出棧順序，達(dá)成我們要訪問的順序結(jié)果
public List<Integer> preOrder2(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
/*
棧解法：前序遍歷，按照根左右的順序
由于棧是先進(jìn)后出，需要調(diào)整入棧順序
1.根節(jié)點(diǎn)（棧頂節(jié)點(diǎn)）直接出棧，加入隊(duì)列
2.我們要的順序：先訪問左節(jié)點(diǎn)（左子樹）再訪問右節(jié)點(diǎn)（右子樹）
3.入棧順序：先加入右節(jié)點(diǎn)，再加入左節(jié)點(diǎn)
*/
while (!stack.isEmpty()) {
TreeNode curNode = stack.pop();
ans.add(curNode.val);
if (curNode.right != null)
stack.push(curNode.right);
if (curNode.left != null)
stack.push(curNode.left);
}
return ans;
}
三、中序遍歷
1. 遞歸寫法
// 中序：遞歸方法遍歷，左根右
public List<Integer> inOrder1(TreeNode root) {
List<Integer> ans = new ArrayList<>();
inOrder_dfs(root, ans);
return ans;
}
public void inOrder_dfs(TreeNode node, List<Integer> ans) {
if (node == null)
return;
// 中序遍歷：從左孩子節(jié)點(diǎn)返回時(shí)，獲取節(jié)點(diǎn)值
preOrder_dfs(node.left, ans);
ans.add(node.val);
preOrder_dfs(node.right, ans);
}
2. 非遞歸寫法
public List<Integer> inOrder2(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
/*
棧解法：中序遍歷，需要按照左根右順序入隊(duì)
對(duì)每一顆子樹，我們都這樣做
1.需要先一直往左遍歷，直到最左側(cè)最深節(jié)點(diǎn)，同時(shí)還要記錄節(jié)點(diǎn)路徑
2.最左最深節(jié)點(diǎn)可以直接獲取值（子樹為空，不需訪問），然后返回上一層節(jié)點(diǎn)（棧中保存記錄）
3.上層節(jié)點(diǎn)此時(shí)可直接獲取值（已經(jīng)從左子樹返回，屬于第二次訪問，該節(jié)點(diǎn)為左子樹的根）
4.在訪問該上層節(jié)點(diǎn)的右節(jié)點(diǎn)，按照123步驟繼續(xù)
*/
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
// 左
while (cur != null) { // 先往左走到最深
stack.push(cur); // 記錄路徑
cur = cur.left;
}
TreeNode node = stack.pop();
ans.add(node.val); // 棧頂元素為該子樹最左最深節(jié)點(diǎn)，直接獲取其值
// 右
if (node.right != null) { // 訪問右子樹
cur = node.right;
}
}
return ans;
}
四、后序遍歷
1. 遞歸寫法
// 后續(xù)：遞歸方法遍歷，左右根
public List<Integer> postOrder1(TreeNode root) {
List<Integer> ans = new ArrayList<>();
postOrder_dfs(root, ans);
return ans;
}
public void postOrder_dfs(TreeNode node, List<Integer> ans) {
if (node == null)
return;
// 后續(xù)遍歷：從右孩子節(jié)點(diǎn)返回時(shí)，獲取節(jié)點(diǎn)值
postOrder_dfs(node.left, ans);
postOrder_dfs(node.right, ans);
ans.add(node.val);
}
2. 非遞歸寫法
public List<Integer> postOrder2(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = root; // 指針cur標(biāo)記當(dāng)前退出的節(jié)點(diǎn)
stack.push(root);
/*
使用棧：后續(xù)遍歷，要求順序，左右根
由于節(jié)點(diǎn)路徑要保留，所以先用peek查看，而不用pop
1.對(duì)每一顆子樹，我們先一直訪問直至其最左最深節(jié)點(diǎn)
2.然后獲取最左最深節(jié)點(diǎn)值，返回上一層
3.在上一層需要進(jìn)行判斷，左子樹和右子樹是否訪問過
我們通過加入節(jié)點(diǎn)記錄值pre，記錄上次退出的節(jié)點(diǎn)
(1)如果上次從左子樹/右子樹退出，表明左子樹不需再訪問
(2)如果上次從右子樹退出，表明右子樹不需再訪問
4.如果滿足條件，繼續(xù)按照上述123步驟，訪問其左子樹/右子樹
*/
while (!stack.isEmpty()) {
TreeNode peek = stack.peek();
// cur = peek是記錄上次退出的節(jié)點(diǎn)
// 如果上次退出的節(jié)點(diǎn)和左/右子節(jié)點(diǎn)相同，則表示那邊的子樹已經(jīng)訪問過了，不需要再訪問
// 左子節(jié)點(diǎn)不為空時(shí)，需要判斷左右節(jié)點(diǎn)是否需要再訪問
// 右節(jié)點(diǎn)不為空時(shí)，此時(shí)已經(jīng)從左節(jié)點(diǎn)返回，不會(huì)再訪問左節(jié)點(diǎn)，故只需判斷右節(jié)點(diǎn)是否需要訪問
if (peek.left != null && peek.left != pre && peek.right != pre) {
stack.push(peek.left); // 往左遍歷
} else if (peek.right != null && peek.right != pre) {
stack.push(peek.right); // 往右遍歷
} else {
ans.add(stack.pop().val); // 左右都空
pre = peek;
}
}
return ans;
}
- 后序遍歷還有一種方法：
- 將前序遍歷左右順序換一下，變?yōu)椋ǜ易螅?/li>
- 然后得到變形的前序遍歷結(jié)果，將結(jié)果反轉(zhuǎn)可以得到后序遍歷（左右根）
- 代碼省略，改一下訪問順序即可
五、層序遍歷
1. 從上到小層序遍歷
// 層序遍歷：從上往下
public List<Integer> levelOrder(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
ans.add(cur.val);
if (cur.left != null)
queue.add(cur.left);
if (cur.right != null)
queue.add(cur.right);
}
}
return ans;
}
2. 從下往上遍歷
// 層序遍歷：從下往上
public List<Integer> levelOrder_desc(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 分層記錄
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
temp.add(cur.val);
if (cur.left != null)
queue.add(cur.left);
if (cur.right != null)
queue.add(cur.right);
}
lists.add(new ArrayList<>(temp));
}
List<Integer> ans = new ArrayList<>();
for (int i = lists.size() - 1; i >= 0; i--) {
List<Integer> l = lists.get(i);
ans.addAll(l);
}
return ans;
}
