199. 二叉树的右视图（C++题解含VS可运行源程序）

• 1.题解
• • 层序遍历
• 2.力扣C++源码
• 3.VS可运行源程序

1.题解

层序遍历

• 层次遍历，取每一层的最右值，就ok了。
• 超级简单。

2.力扣C++源码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        //层次遍历的方法，只要取每一层的最右值
        //参考102. 二叉树的层序遍历
        if (!root)return {};
        vector<int> temp;
        vector<int> res;
        queue<TreeNode*> store;
        store.push(root);
        int remaining = 1;
        int nextlevel = 0;

        while (!store.empty()) {
            TreeNode* node = store.front();
            store.pop();
            remaining--;
            temp.push_back(node->val);

            if (node->left) {
                store.push(node->left);
                nextlevel++;
            }
            if (node->right) {
                store.push(node->right);
                nextlevel++;
            }
            if (!remaining) {
                remaining = nextlevel;
                nextlevel = 0;
                res.push_back(temp.back());
                temp.clear();
            }
        }
        return res;
    }
};

3.VS可运行源程序

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<algorithm>
#include<math.h>
#pragma warning(disable:4996)
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
	vector<int> rightSideView(TreeNode* root) {
        //层次遍历的方法，只要取每一层的最右值
        //参考102. 二叉树的层序遍历
        if (!root)return {};
        vector<int> temp;
        vector<int> res;
        queue<TreeNode*> store;
        store.push(root);
        int remaining = 1;
        int nextlevel = 0;

        while (!store.empty()) {
            TreeNode* node = store.front();
            store.pop();
            remaining--;
            temp.push_back(node->val);

            if (node->left) {
                store.push(node->left);
                nextlevel++;
            }
            if (node->right) {
                store.push(node->right);
                nextlevel++;
            }
            if (!remaining) {
                remaining = nextlevel;
                nextlevel = 0;
                //只需要在(102层序遍历)的基础上改一下这行代码即可
                res.push_back(temp.back());//取每一层的最右值
                temp.clear();
            }
        }
        return res;
	}
};
//递归方式创建与遍历
void CreateBiTree2(TreeNode** T)//传的是根指针的指针，这样不用返回值了就
{
    int val;
    scanf("%d", &val);
    if (val == -1)//将叶子节点都设为-1，作为判断输入终止标志，#这个根节点就是NULL
        *T = NULL;//*T就是BiTree T的T或者是BiTNode* T的T
    else
    {
        *T = (TreeNode*)malloc(sizeof(TreeNode));
        if (!*T)//开辟空间失败就退出
            exit(-1);
        (*T)->val = val;
        CreateBiTree2(&(*T)->left);//递归创建
        CreateBiTree2(&(*T)->right);
    }
}
int main()
{
    printf("按先序遍历顺序输入二叉树（叶子节点的左右孩子节点均输入-1）：\n");
    TreeNode* T;
    CreateBiTree2(&T);//地址传递，传根节点指针的地址
    Solution test;
    vector<int> ans;
    ans = test.rightSideView(T);
    printf("二叉树的右视图为：");
    for (int i = 0; i < ans.size(); i++) {
        printf("%d ", ans[i]);
    }

	printf("\n");
	system("pause");
	return 0;
}