LeetCode 199 二叉树的右视图

199.二叉树的右视图

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

1.1 DFS实现

在本题中使用DFS实现存在一定的难度，但是也不失为一种实现方式，基本思想为：采用根右左的方式进行深度优先搜索，那么在第一次到达新的一层时，访问的节点就是二叉树每层的最右侧节点。那么在DFS中需要做的是就是判断，何时时第一次当前层的。

class Solution {
public:
    //深度优先遍历
    vector<int> ret;
    void _rightView(TreeNode* node, int depth) {
        if (node == nullptr) return;
        if (ret.size() == depth) ret.emplace_back(node->val);
        if (node->right) _rightView(node->right, depth + 1);
        if (node->left) _rightView(node->left, depth + 1);
    }
    vector<int> rightSideView(TreeNode* root) {
        _rightView(root, 0);
        return ret;
    }
};

上述代码在实现上的巧妙性就在于：初始时传递的深度值为0，那么深度为n时，第一次到达n层，对应的数组的长度也是n，若不是第一次到达，那么数组的长度肯定是n+1，本质上是利用了数据中长度信息来记录是不是第一次到达当前层。

1.2 BFS实现

使用BFS能够在当前层中找到层的最后一个元素，此时就只需要将相应的元素添加到序列中即可。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int levelSize=q.size();
            TreeNode *node;
            for(int i=0;i<levelSize;i++){
                node=q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            if(node) ans.push_back(node->val);
        }
        return ans;
    }
};