subject

leetcode Original link

Given a binary tree The root node root, Imagine yourself on the right side of it , In order from top to bottom , Returns the value of the node as seen from the right .

Example 1:

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

Example 2:
Input : [1,null,3]
Output : [1,3]

Example 3:
Input : []
Output : []

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

Ideas

• Think about it , Look from right to left , What are the characteristics of the nodes you see ？ Each layer can see only one node , And this node is the last node of each layer .
• Based on the above analysis , Obviously, the sequence traversal of binary tree is enough. When the last node of each layer is encountered , Just add the node to the result array .

Code

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/** * @param {TreeNode} root * @return {number[]} */
var rightSideView = function(root) {
    
    if(!root) return []
    let queue = [root]
    let res = []
    while(queue.length){
    
        const len = queue.length
        for(let i = 0 ; i < len ; i++){
    
            const curNode = queue.shift()
            if(i === len - 1) res.push(curNode.val) // Determine whether to be the last node of the layer , If so, save it 
            if(curNode.left) queue.push(curNode.left)
            if(curNode.right) queue.push(curNode.right)
        }
    }

    return res
};

Complexity

• Time complexity ：$O(n)$
• Spatial complexity ：$O(n)$

Pay attention to my special column , Update three times a day leetcode Answer key , Get stronger together ！