RightSideView.cpp

#include<iostream>
#include<string>
#include<string.h>
#include<stack>
#include<assert.h>
#include<queue>
#include<unordered_map>
#include<algorithm>
#include<sstream>

using namespace std;

/**
 * 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) {}
 * };
 */
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) {
	unordered_map<int, int> rightmostValueAtDepth;
	int max_depth = -1;
	queue<TreeNode*> nodeQueue;
	queue<int> depthQueue;
	nodeQueue.push(root);
	depthQueue.push(0);

	while(!nodeQueue.empty()) {
	    TreeNode *node = nodeQueue.front();
	    nodeQueue.pop();
	    int depth = depthQueue.front();
	    depthQueue.pop();

	    if(node != nullptr) {
	        max_depth = max(max_depth, depth);
		rightmostValueAtDepth[depth] = node->val;

		nodeQueue.push(node->left);
		depthQueue.push(depth+1);
		nodeQueue.push(node->right);
		depthQueue.push(depth+1);
	    }
	}
	vector<int> rightView;
	for(int depth = 0; depth <= max_depth; ++depth) {
	    rightView.push_back(rightmostValueAtDepth[depth]);
	}
	return rightView;
    }
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}
//举例:[1,2,3,null,5,null,4]
TreeNode* stringToTreeNode(string input) {
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);//去掉[1,2,3,null,5,null,4]中的前面的[和最后的],变为:1,2,3,null,5,null,4;
    if (!input.size()) {
        return nullptr;
    }

    string item;
    stringstream ss;
    ss.str(input);

    getline(ss, item, ',');                         //取出root对应的第一个字符'1'存入item；
    cout << "item =" << item << endl;
    TreeNode* root = new TreeNode(stoi(item));
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);

    while (true) {                                  //层次遍历创建二叉树
        TreeNode* node = nodeQueue.front();
        nodeQueue.pop();

        if (!getline(ss, item, ',')) {              //读取左孩子的字符;
            break;
        }
        //cout << "item =" << item << endl;
        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int leftNumber = stoi(item);
            node->left = new TreeNode(leftNumber); //创建左孩子
            nodeQueue.push(node->left);
        }

        if (!getline(ss, item, ',')) {             //读取右孩子的字符;
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int rightNumber = stoi(item);
            node->right = new TreeNode(rightNumber); //创建右孩子
            nodeQueue.push(node->right);
        }
    }
    return root;
}

string integerVectorToString(vector<int> list, int length = -1) {
    if (length == -1) {
        length = list.size();
    }

    if (length == 0) {
        return "[]";
    }

    string result;
    for(int index = 0; index < length; index++) {
        int number = list[index];
        result += to_string(number) + ", ";
    }
    return "[" + result.substr(0, result.length() - 2) + "]";
}

int main() {
    string line;
    while (getline(cin, line)) {
        TreeNode* root = stringToTreeNode(line);
        
        vector<int> ret = Solution().rightSideView(root);

        string out = integerVectorToString(ret);
        cout << out << endl;
    }
    return 0;
}