LeetCode 199

image.png

思路一：BFS

我们可以利用二叉树的层次遍历，只保留每一层的最后一个节点即可，这就是广度优先搜索的方法。

  1. var rightSideView = function(root) {
  2.     if(!root) return [];
  4.     let res = [];
  5.     let queue = [root];
  7.     while(queue.length) {
  8.         let size = queue.length;
  9.         res.push(queue[0].val)
  10.         while(size--) {
  11.             let cur = queue.shift();
  12.             if(cur.right) queue.push(cur.right);    // 先放右节点
  13.             if(cur.left) queue.push(cur.left);        // 再放左节点
  14.         }
  15.     }
  16.     return res;
  17. };

思路二：DFS

按照 [根节点 -> 右节点 -> 左节点] 的顺序访问，就可以保证每次都是最先访问右边的节点。

这里需要注意 depth===res.length 这句代码。
因为我们每层肯定是最先访问最右边的节点的，因此当前为符合条件的节点时，它肯定能放进 res 中。而当到了左节点时，因为我们已经放进去右节点了，depth 与 res.length 必不可能相等了，因此它放不进 res 中。

  1. var rightSideView = function(root) {
  2.     let res = []
  3.   dfs(root, 0, res);
  4.   return res;
  5. }
  7. function dfs(root, depth, res) {
  8.     if(!root)    return;
  10.   // 如果当前节点深度还没出现在res中，则说明该节点是当前层次第一个被访问到的节点
  11.   // 而第一个被访问到的节点，肯定的最右边的节点
  12.   if(depth === res.length)
  13.     res.push(root.val);
  15.   depth++;
  16.   dfs(root.right, depth, res);
  17.   dfs(root.left, depth, res);
  18. }