199. Binary Tree Right Side View

Leetcode

https://leetcode.com/problems/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: []

解答

• 方法一

用 level 記錄每層的層數，由右邊先行遍歷，如此一來只要第一次遍歷到的節點且原本在相對應的 level 上沒有數值，就是同層最右邊的節點

var rightSideView = function(root) {
    if(!root) return [];
    
    const res = [];
    const queue = [root];
    
    let level = 0;
    while(queue.length) {
        const len = queue.length;
        for(let i=0; i<len; i++) {
            const node = queue.shift();
            if (res[level] === undefined) {
                res[level] = node.val;
            }
            if(node.right) queue.push(node.right);
            if(node.left) queue.push(node.left);
        }
        level++;
    }
    
    return res;
};

Runtime: 100 ms, faster than 31.84% of JavaScript online submissions for Binary Tree Right Side View.

Memory Usage: 43.9 MB, less than 57.38% of JavaScript online submissions for Binary Tree Right Side View.

• 方法二

DFS

var rightSideView = function(root) {
    const res = [];
    const dfs = (node, level) => {
        if (!node) return;
        if (res[level] === undefined) {
            res[level] = node.val;
        };
        dfs(node.right, level+1);
        dfs(node.left, level+1);
    }
    
    dfs(root, 0);
    return res;
};

Runtime: 87 ms, faster than 52.33% of JavaScript online submissions for Binary Tree Right Side View.

Memory Usage: 43.8 MB, less than 67.93% of JavaScript online submissions for Binary Tree Right Side View.