DFS深度優(yōu)先算法
簡(jiǎn)單的理解深度優(yōu)先算法遍歷樹結(jié)構(gòu)，算法從節(jié)點(diǎn)出發(fā)沿著子節(jié)點(diǎn)一直往下走羽德，走到?jīng)]有字節(jié)點(diǎn)為止開始返回，即一直走到樹的最深處（葉節(jié)點(diǎn)）章蚣，然后開始往前返回值姨夹。
遞歸DFS
深度優(yōu)先算法的遞歸表示十分簡(jiǎn)潔纤垂，理解遞歸DFS十分有助于理解樹結(jié)構(gòu)以及遞歸。
public void dfsRecursive(TreeNode root){
//對(duì)于遞歸算法贾虽，basecase是首要考慮的
if (root==null) return ans;
//在兩次遞歸之前fc進(jìn)行操作即為前序遍歷
dfsRecursive(root.left);
System.out.println(root.val);//在兩次遞歸之間進(jìn)行操作即為中序遍歷
dfsRecursive(root.right);
//在兩次遞歸之后進(jìn)行操作即為后序遍歷
return ans;
}
非遞歸DFS
根據(jù)DFS的定義吼鱼，DFS一路往深處走，并記錄走過的節(jié)點(diǎn)菇肃，走到底時(shí)再進(jìn)行彈出并輸出。因此很容易想到需要使用棧結(jié)構(gòu)巷送。
public void dfs(TreeNode root) {
if(root==null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (stack.size() > 0) {
TreeNode node = stack.pop();
//同樣的如果要進(jìn)行的操作在遞歸之前，那么就是前序遍歷付魔，見名知意
System.out.println(node.val);
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);
}
}
通過DFS遞歸與非遞歸的算法可以很容易的完成非撤甚澹基礎(chǔ)的leetcode樹的遍歷題
BFS廣度優(yōu)先算法（非遞歸）
廣度優(yōu)先算法BFS，又稱層序遍歷陈哑，正如其名，按一層一層遍歷樹結(jié)構(gòu)惊窖，一般情況下只有非遞歸的表達(dá)，由于其算法按層遍歷的特性圣拄，其中用到的數(shù)據(jù)結(jié)構(gòu)為Queue隊(duì)列，因此遞歸的表達(dá)較為復(fù)雜庇谆。
public void bfs(TreeNode root) {
if (root == null) return void;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (queue.size() > 0) {
for (int i = 0; i < queue.size(); i++) {
TreeNode node = queue.poll();
System.out.println(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
}
leetcode關(guān)于bfs的題目,這里推薦兩道十分基礎(chǔ)的便于熟悉算法：
- 102. 二叉樹的層序遍歷
-
劍指 Offer 55 - I
BFS與DFS都是圖以及樹中的十分基礎(chǔ)卻又十分強(qiáng)大的算法凭疮，熟練掌握這兩個(gè)算法便已經(jīng)可以解決不少leetcode中關(guān)于樹和題的問題。
