Leetcode Study Day 39

Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:


Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2:

Input: root = [1,null,3]
Output: [1,3]
Example 3:

Input: root = []
Output: []
 

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution

The solution calls a function “recursion”. In this function, it will first check if the node is null. If it is null, it will return. If the size of the answer vector is smaller than the level, it will push the value of the node into the vector, which means it will check whether at this level of the tree, there is already has a node on the most right side (in the array). Then it will call the recursion function on the right subtree and left subtree. The order is right first and then left. The reason is that we want to push the node on the most right side into the vector first.

One thing to notice is that we should pass the address of the vector into the function (&ans). Otherwise, the vector will not be changed.

/**
 * 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:
    void recursion(TreeNode* node, int level, vector<int> &ans){
        if(!node) return;
        if(ans.size()<level)
            ans.push_back(node->val);
        recursion(node->right,level+1,ans);
        recursion(node->left,level+1,ans);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector <int> ans;
        recursion(root,1,ans);
        return ans;
    }
};