一、深度優先遍歷二叉樹
1.前序遍歷（先添加根節點的值，然后添加左右節點的值）
1.1.遞回遍歷
1.1.1.思路
遞回遍歷二叉樹相對簡單:
- 考慮特殊情況：當根節點為空的時候，直接回傳null
- 如果根不為空，則將根的值添加進入List
- 判斷左右節點是否為空，非空則開始遞回
- 遞回的方法：用于判斷是否還有左右節點，添加節點的值，有節點則繼續遞回，沒有則回傳上一個節點
DFS（）引數：node.left，node.right
無回傳值，因為List是參考型別，所以不用回傳值，直接添加值
1.1.2.代碼
點擊查看代碼
//遞回 二叉樹的前序遍歷
import java.util.LinkedList;
import java.util.List;
class Solution2 {
//定義一個鏈表用來接收答案
LinkedList<Integer> list = new LinkedList<>();
public List<Integer> preorderTraversal(TreeNode root) {
//考慮特殊情況
if(root==null)return list;
list.add(root.val);
//如果左邊不為空就先對左邊進行深度優先查詢
if (root.left != null) {
DFS(root.left);
}
if (root.right != null) {
DFS(root.right);
}
return list;
}
//1\首先處理傳入的值
//2\在進行下一步判斷和呼叫遞回
public void DFS(TreeNode node) {
list.add(node.val);
if (node.left!= null) {
DFS(node.left);
}
if (node.right != null) {
DFS(node.right);
}
}
}
1.2.迭代遍歷
1.2.1.思路
相對與遞回，迭代會更麻煩:
- 考慮特殊情況
- 定義一個堆疊用來存盤樹的節點，一個鏈表接受變數
- 使用兩個while回圈，每次遍歷到最后一個節點以后就從堆疊poll一個樹節點，即回傳上一個節點，然后繼續遍歷，
1.2.2.代碼
點擊查看代碼
//不用遞回,而是用迭代查詢
import java.util.*;
class Solution1 {
//定義一個堆疊(stack已經過時,而deque是stack的升級版),用來存盤節點,目的是可以回傳上一個節點
//定義一個鏈表,用來存盤節點的值,最后的答案
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<Integer> list=new LinkedList<>();
//特殊情況
if(root==null)return list;
Deque<TreeNode> stack=new LinkedList<>();
stack.push(root);
TreeNode node=root;
//這里是重點,如果node是空,則將堆疊中節點推出,回傳上一個節點
//如果node非空,則推入堆疊中方便回傳上一個節點,繼續向左邊遍歷
while(!stack.isEmpty()){
while(node!=null){
list.add(node.val);
stack.push(node);
node=node.left;
}
node=stack.pop();
node=node.right;
}
return list;
}
}
2.中序遍歷（先添加左節點的值，在添加根節點的值，最后添加右節點的值）
2.1.遞回遍歷
2.1.1.思路
與前序遍歷的思路一樣，但是添加值的位置改變了:
2.1.2.代碼
點擊查看代碼
class Solution3 {
public List<Integer> inorderTraversal(TreeNode root) {
LinkedList<Integer> list = new LinkedList<>();
if (root == null) return list;
if (root.left != null) {
DFS(root.left, list);
}
list.add(root.val);
if (root.right != null) {
DFS(root.right, list);
}
return list;
}
private void DFS(TreeNode node, LinkedList<Integer> list) {
if (node.left != null) {
DFS(node.left, list);
}
list.add(node.val);
if (node.right != null) {
DFS(node.right, list);
}
}
}
3.后序遍歷（先添加左右節點的值，最后添加根節點的值）
3.1.遞回遍歷
3.1.1.思路
與前面的前序遍歷和中序遍歷相差不大，依然是換了添加值的位置:
3.1.2.代碼
點擊查看代碼
//后續遍歷，遞回
import java.util.LinkedList;
import java.util.List;
class Solution4 {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> list=new LinkedList<>();
if(root==null)return list;
if(root.left!=null)DFS(root.left,list);
if(root.right!=null)DFS(root.right,list);
list.add(root.val);
return list;
}
private void DFS(TreeNode node,List<Integer> list){
if(node.left!=null)DFS(node.left,list);
if(node.right!=null)DFS(node.right,list);
list.add(node.val);
}
}
二、廣度優先遍歷二叉樹
1.層序遍歷
1.1思路
使用廣度優先進行遍歷:
- 第一步依然是考慮特殊情況
- 創建一個佇列和一個鏈表，佇列用于添加節點，鏈表用來添加答案
- 首先將根節點添加進答案
- 創建一個while回圈，只要佇列不為空，則不斷將節點的值添加進答案中
- 在while里面創建一個for回圈，每次遍歷poll出樹的一層節點，并添加下一層節點（在for前面要提前宣告一個size來得到當前層的節點數，第一次遍歷在這里卡了好久）
1.2代碼
點擊查看代碼
class Solution2 {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
LinkedList<List<Integer>> answer = new LinkedList<>();
if (root == null) return answer;
queue.add(root);
LinkedList<Integer> rootlist = new LinkedList<Integer>();
rootlist.add(root.val);
answer.add(rootlist);
while (!queue.isEmpty()) {
// LinkedList<Integer> list=new LinkedList<>();
// while(!queue.isEmpty()) {1
// node = queue.poll();
// if (node.left != null) {
// list.add(node.left.val);
// }
// if (node.right != null) {
// list.add(node.right.val);
// }
// queue.add(node.left);
// queue.add(node.right);
// if (!list.isEmpty()) answer.add(list);
//
// }
//遇到的問題：如何讓一個list添加一層的節點的值而不是一個節點下面的兩個節點的值的值？
LinkedList<Integer> list = new LinkedList<>();
//可以利用queue.size，指定一個size次的for回圈，這樣poll()出去的節點就是上一層的所有節點
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
list.add(node.left.val);
queue.add(node.left);
}
if (node.right != null) {
list.add(node.right.val);
queue.add(node.right);
}
}
//而list內的值也是當前層的值
if (!list.isEmpty()) answer.add(list);
//一次for之后，queue里面的節點是當前層的節點，因為上一層的size個節點已經被poll()出去了
}
return answer;
}
}
三、文章內容的梳理
相關練習可以在LeetCode上面找到
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/319596.html
標籤：其他
上一篇：2021熱乎的位元組跳動軟體測驗工程師面試題及答案分享
下一篇：數值分析：矩陣奇異值分解