[leetcode] Binary Tree Right Side View


Binary Tree Right Side View

Given 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.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

DFS, visit current node, then right child, then left node.

Store the current level number we are visiting, starting with 1.

if ans.size() > level, do not output, we can’t see this current node in the right view.

else output this node.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        DFS(root, ans, 1);
        return ans;
    }
    void DFS(TreeNode * root, vector<int>& ans, int level){
        if(root == NULL){
            return ;
        }
        if(level > ans.size()){
            ans.push_back(root->val);
        }
        DFS(root->right, ans, level + 1);
        DFS(root->left, ans, level + 1);
    }
};

 

 

Untitled

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.