LeetCode每日一題之二叉樹的右視圖

覺得可以的小夥伴可以關注下個人公眾號，堅持每日完成自己的原創分享。

堅持原創分享

199. 二叉樹的右視圖

難度中等176

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

示例:

<code>
輸入:
 
[1,2,3,null,5,null,4]
輸出:
 
[1,
 
3
,
 
4
]
解釋:

   
1
            

 
/
   
\
2
      
3
         

 
\
     
\
  
5
     
4
       

/<code>

https://leetcode-cn.com/problems/binary-tree-right-side-view/

純手打記錄自己解題思路：

通過深度遍歷獲取每一行的最右側節點，這裡需要體現兩點：1、每一行 2、最右側。

• 如何體現每一行：通過記錄深度來達到對行的體現

• 如何體現最右側：通過建立 Map 來記錄每一行中的元素，通過對當前樹逆後序遍歷【自己的定義方式：就遍歷根節點後遍歷右子樹直到葉子節點，再遍歷左子樹直到葉子節點】遍歷到的當前行記錄第一個add 到 map 的元素即為右側看到的第一個元素。

整體的思路還是比較簡單的，追根節點還是遞歸，只不過用了 map 來臨時存儲，代碼如下：

<code>純手打記錄自己解題思路：

通過深度遍歷獲取每一行的最右側節點，這裡需要體現兩點：
1
、每一行 
2
、最右側。
如何體現每一行：通過記錄深度來達到對行的體現
如何體現最右側：通過建立 Map 來記錄每一行中的元素，通過對當前樹逆後序遍歷【自己的定義方式：就遍歷根節點後遍歷右子樹直到葉子節點，再遍歷左子樹直到葉子節點】遍歷到的當前行記錄第一個add 到 
map
 的元素即為右側看到的第一個元素。
整體的思路還是比較簡單的，追根節點還是遞歸，只不過用了 
map
 來臨時存儲，代碼如下：

 
class
 
Solution
 {

 
    
private
 HashMap  
map
 = 
new
 HashMap();
    
public
 List rightSideView(TreeNode root) {
         
        helper(root,
0
);
         
         
return
 
new
 ArrayList(
map
.values());
    }

    
private
 
void
 
helper
(TreeNode root,Integer depth)
{
        
if
(root != null) {
            depth++;
             
            
if
(!
map
.containsKey(depth)) 
map
.put(depth, root.val);
            
if
(root.right != null) helper(root.right, depth);
            
if
(root.left != null) helper(root.left, depth);
        }

    }
}
/<code>

作者：kirago

鏈接：
https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/shen-du-you-xian-di-gui-dfsji-yi-cun-chu-by-kirago/

來源：力扣（LeetCode）

著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。