LeetCode-199. 二叉树的右视图

一、题目描述

二、解题方法

• 显然采用层次遍历，所谓右视图，也就是每一层的最后一个节点。
• 每次进入循环，记录一下队列中的数据个数，最后一个数据便是本层最后一个节点

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

• 这道题还可以用递归来求解，每次递归将每层最右面的节点找到，然后加入vector
  • 保证vector的长度和当前所在层次相同
  • 这里注意在向下递归时，要先递归右子树，后递归左子树
  • 如果有右子树，那么递归左子树时，vector的长度因为别右子树加了1，当前所在层次和其不相等，无效
  • 如果没有右子树，回归到上一种情况

class Solution {
public:
    vector<int> rightSideView(TreeNode* root){
        vector<int> sln;
        GetRightNode(root, sln, 0);
        return sln;
    }
private:
    void GetRightNode(TreeNode* root, vector<int> &sln, int depth){
        if(!root)   return;
        if(depth == sln.size()){
            sln.push_back(root->val);
        }
        GetRightNode(root->right, sln, depth + 1);
        GetRightNode(root->left, sln, depth + 1);
    }
};

三、运行结果

前一个递归做法，后一个是正常层次遍历