【leetcode】【剑指offer Ⅱ】046. 二叉树的右侧视图

问题描述：

• 给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

核心思路：

• 二叉树基础应用题，和剑指 offer Ⅱ 045 是一样的。
  • bfs 解题，在每一层的结尾更新数组结果。【或者在元素入队列的时候先右子入队列再左子入队列，如此最右边元素便成为每一层的第一个访问元素】
  • dfs 解题，同理，可以先递归进入右子再递归进入左子，当第一次访问到的高度时把节点值存入结果数组中。【即根据根右左的访问方式进行 dfs 访问】

代码实现：

• bfs 解法代码实现如下：

  class Solution
  {
  public:
      vector<int> rightSideView(TreeNode* root)
      {
          vector<int> ans;
          if(!root) return ans;
          queue<TreeNode*> q;
          q.push(root);
          TreeNode* tmp;
          while(!q.empty())
          {
              int sz = q.size();
              while(sz-- > 0)
              {
                  tmp = q.front(); q.pop();
                  if(sz == 0) ans.emplace_back(tmp->val);
                  if(tmp->left) q.push(tmp->left);
                  if(tmp->right) q.push(tmp->right);
              }
          }
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24