# 0199. 二叉樹的右視圖 ## 題目地址(199. 二叉樹的右視圖) <https://leetcode-cn.com/problems/binary-tree-right-side-view/> ## 題目描述 ``` <pre class="calibre18">``` 給定一棵二叉樹，想象自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。 示例: 輸入: [1,2,3,null,5,null,4] 輸出: [1, 3, 4] 解釋: 1 <--- / \ 2 3 <--- \ \ 5 4 <--- ``` ``` ## 前置知識 - 隊列 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 > 這道題和 leetcode 102 號問題《102.binary-tree-level-order-traversal》很像 這道題可以借助`隊列`實現，首先把 root 入隊，然后入隊一個特殊元素 Null(來表示每層的結束)。 然后就是 while(queue.length), 每次處理一個節點，都將其子節點（在這里是 left 和 right）放到隊列中。 然后不斷的出隊， 如果出隊的是 null，則表式這一層已經結束了，我們就繼續 push 一個 null。 ## 關鍵點解析 - 隊列 - 隊列中用 Null(一個特殊元素)來劃分每層 - 樹的基本操作- 遍歷 - 層次遍歷（BFS） - 二叉樹的右視圖可以看作是層次遍歷每次只取每一層的最右邊的元素 ## 代碼 語言支持：JS，C++ Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * @param {TreeNode} root * @return {number[]} */</span> <span class="hljs-keyword">var</span> rightSideView = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">root</span>) </span>{ <span class="hljs-keyword">if</span> (!root) <span class="hljs-keyword">return</span> []; <span class="hljs-keyword">const</span> ret = []; <span class="hljs-keyword">const</span> queue = [root, <span class="hljs-params">null</span>]; <span class="hljs-keyword">let</span> levelNodes = []; <span class="hljs-keyword">while</span> (queue.length > <span class="hljs-params">0</span>) { <span class="hljs-keyword">const</span> node = queue.shift(); <span class="hljs-keyword">if</span> (node !== <span class="hljs-params">null</span>) { levelNodes.push(node.val); <span class="hljs-keyword">if</span> (node.right) { queue.push(node.right); } <span class="hljs-keyword">if</span> (node.left) { queue.push(node.left); } } <span class="hljs-keyword">else</span> { <span class="hljs-title">// 一層遍歷已經結束</span> ret.push(levelNodes[<span class="hljs-params">0</span>]); <span class="hljs-keyword">if</span> (queue.length > <span class="hljs-params">0</span>) { queue.push(<span class="hljs-params">null</span>); } levelNodes = []; } } <span class="hljs-keyword">return</span> ret; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>> rightSideView(TreeNode* root) { <span class="hljs-keyword">auto</span> ret = <span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>(); <span class="hljs-keyword">if</span> (root == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> ret; <span class="hljs-keyword">auto</span> q = <span class="hljs-params">queue</span><<span class="hljs-keyword">const</span> TreeNode*>(); q.push(root); <span class="hljs-keyword">while</span> (!q.empty()) { <span class="hljs-keyword">auto</span> sz = q.size(); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> i = <span class="hljs-params">0</span>; i < sz; ++i) { <span class="hljs-keyword">auto</span> n = q.front(); q.pop(); <span class="hljs-keyword">if</span> (n->left != <span class="hljs-params">nullptr</span> ) q.push(n->left); <span class="hljs-keyword">if</span> (n->right != <span class="hljs-params">nullptr</span> ) q.push(n->right); <span class="hljs-keyword">if</span> (i == sz - <span class="hljs-params">1</span>) ret.push_back(n->val); } } <span class="hljs-keyword">return</span> ret; } }; ``` ``` ## 擴展 假如題目變成求二叉樹的左視圖呢？ 很簡單我們只需要取 queue 的最后一個元素即可。 或者存的時候反著來也行 > 其實我們沒必要存儲 levelNodes，而是只存儲每一層最右的元素，這樣空間復雜度就不是 n 了， 就是 logn 了。