生活随笔
收集整理的這篇文章主要介紹了
深度优先和广度优先算法（例题）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
在LeetCode上面刷題刷到一道二叉樹的題，這道題我認為對學習樹的深度優先和廣度優先算法有一定的幫助，先來看一下題
這道題是這樣的：
給定一棵二叉樹，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。
這道題有兩種思路一種是深度優先一種是廣度優先
深度優先
見名知意這種思路就是先從深度遍歷，我們先去往深處遍歷，由于這道題是尋找每一層最右面的值，我們可以總是先訪問右子樹。這樣就保證了當我們訪問樹的某個特定深度時，我們正在訪問的節點總是該深度的最右側節點。于是，可以存儲在每個深度訪問的第一個結點，一旦我們知道了樹的層數，就可以得到最終的結果。
代碼如下：
class Solution {public List
<Integer> rightSideView(TreeNode root
) {Map
<Integer, Integer> map
= new HashMap<Integer, Integer>();int max_depth
= -1;Stack
<TreeNode> nodeStack
= new Stack<TreeNode>();Stack
<Integer> depthStack
= new Stack<Integer>();nodeStack
.push(root
);depthStack
.push(0);while (!nodeStack
.isEmpty()) {TreeNode node
= nodeStack
.pop();int depth
= depthStack
.pop();if (node
!= null
) {max_depth
= Math
.max(max_depth
, depth
);if (!map
.containsKey(depth
)) {map
.put(depth
, node
.val
);}nodeStack
.push(node
.left
);nodeStack
.push(node
.right
);depthStack
.push(depth
+1);depthStack
.push(depth
+1);}}List
<Integer> rightView
= new ArrayList<Integer>();for (int depth
= 0; depth
<= max_depth
; depth
++) {rightView
.add(map
.get(depth
));}return rightView
;}
}
廣度優先
同樣很容易看到這個詞的1意思，就是從寬度下手，跟深度優先正好相反，每一層每一層的去遍歷，直到最后一層，我們對每一層都從左到右訪問。因此，通過只保留每個深度最后訪問的結點，我們就可以在遍歷完整棵樹后得到每個深度最右的結點。
代碼如下：
class Solution {public List
<Integer> rightSideView(TreeNode root
) {List
<Integer>list
=new ArrayList<Integer>();if(root
==null
)return list
;int level
=0;Queue
<TreeNode> queue
= new LinkedList<TreeNode>();queue
.add(root
);while ( !queue
.isEmpty() ) {int level_length
= queue
.size();for(int i
= 0; i
< level_length
; ++i
) {if(i
==level_length
-1){list
.add(queue
.peek().val
);}TreeNode node
= queue
.remove();if (node
.left
!= null
) queue
.add(node
.left
);if (node
.right
!= null
) queue
.add(node
.right
); }level
++;}return list
;}
}
上面是這個題的兩種解法，一個使用的是棧一個使用的是隊列，分別應用了棧后入先出的特向和隊列先進先出的特性，上面的關鍵點已經標出，只要花時間就可以看懂，這道題難度不高，我認為可能對DFS和BFS有一定的理解
總結
以上是生活随笔為你收集整理的深度优先和广度优先算法（例题）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
