目錄

題目：

我們直接看題解吧：

快速理解解題思路小建議：

審題目+事例+提示：

解題方法：

解題分析：

解題思路：

代碼實現(DFS)：

代碼1：

補充說明：

代碼2：

代碼實現(BFS)：

---

題目地址：

199. 二叉樹的右視圖 - 力扣（LeetCode）

難度：中等

今天刷二叉樹的右視圖，大家有興趣可以點上面鏈接，看看題目要求，試著做一下。

題目：

給定一個二叉樹的?根節點?root，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。

我們直接看題解吧：

快速理解解題思路小建議：

可以先簡單看一下解題思路，然后照著代碼看思路，會更容易理解一些。

審題目+事例+提示：

根據題意可知，我們右視圖看到的節點都是每一層的最右邊的節點，而這個節點可能在右子樹，也可能子左子樹

解題方法：

方法1：深度優先（DFS）

方法2：廣度優先（BFS）

解題分析：

我們利用深度優先算法遞歸遍歷二叉樹，按照【根節點->右子樹->左子樹】的順序訪問。

解題思路：

?創建一個list集合res用于存儲右視圖看到的節點（即每層最右邊的節點）

?創建一個臨時遍歷depth,用于記錄遍歷樹的深度

?遞歸函數：

? ? ?首先判斷如果根節點為Null,則直接返回

? ? 接著判斷depth與res.size是否相等，相等則將當前節點加入res

? ?然后depth++,遍歷右子樹、左子樹

代碼實現(DFS)：

代碼1：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*///DFS深度優先算法
class Solution {//先創建一個list集合存儲數據作為返回List<Integer> res = new ArrayList<Integer>();public List<Integer> rightSideView(TreeNode root) {//傳入根節點root，以及0（即depth初始為0）dfs(root,0);return res;}public void dfs(TreeNode root,int depth){//先判斷，1、根節點是否為null，如果根節點為null則返回，//       2、同時也是遞歸的終止條件，即訪問到葉子結點的下一個的時候為null，則返回if(root == null){return;}//首先先訪問當前結點，再遞歸地訪問右子樹 和 左子樹if(depth == res.size()){//判斷二者是否相等，相等則將當前節點加入集合resres.add(root.val);}//每遞歸一次就說明走到下一層，即深度+1depth++;//先遞歸右子樹，再遞歸左子樹，這樣每一層都能訪問到最右邊的結點dfs(root.right,depth);dfs(root.left,depth);}
}

補充說明：

1、遞歸函數第一部分的判空操作的作用

? ? a.根節點判空條件，即如果根節點為null則返回，
? ? b.作為遞歸的終止條件，即訪問到葉子結點的下一個的時候為null，則返回

2、實際上遍歷完右子樹，回過頭遍歷左子樹的時候，depth實際上是從頭計算的，因為一開始遍歷右子樹時，每一次遞歸depth+1，那么最后回溯時depth相當于depth+1直到根節點

2、為什么depth==res.size時，就將當前節點添加到集合res（還是無法理解可以看看下面代碼2）

以此圖為例

首先遍歷右子樹，depth和res.size初始值均為0，根據代碼自上而下的執行順序，res.size首先+1即添加根節點，接著時depth+1，進入下一層，此時res.size==depth==1,因此添加當前節點，接著depth+1...

遍歷完右子樹后，遍歷左子樹，由于depth從0開始，在同一層時，depth與res.size差1，這樣就可以更新新的節點（即depth!=res.size時說明這一層已經有值在res了），同時又能保證每一層只會取到一個節點，（此外由于遍歷順序為根右左，因此保證了每層最先遍歷的時最右邊的節點）

代碼2：

這個的跟上面區別在于用了兩個變量，一個變量maxDepth記錄已探索到的最大深度，和當前的深度depth，只有depth>maxDepth才往list里面add即可。這種可能更好理解一點

 class Solution {//0ms 100% On O1int maxHigh = 0;List<Integer> res = new ArrayList<Integer>();public List<Integer> rightSideView(TreeNode root) {dfs(root,1);return res;}public void dfs(TreeNode root,int high){if(root == null) return;if(maxHigh < high){res.add(root.val);maxHigh = high;}dfs(root.right,high+1);dfs(root.left,high+1);}
}

代碼實現(BFS)：

這里BFS實際上是層次遍歷，然后將每層的最后一個節點加入集合

還有就是創建了一個隊列queue用于存儲每層遍歷的節點

層次遍歷-->二叉樹的層序遍歷，力扣-CSDN博客

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}if (i == size - 1) {  //將當前層的最后一個節點放入結果列表res.add(node.val);}}}return res;}
}