199. Binary Tree Right Side View

Leetcode link

题目简介

/**
 * @param {TreeNode} root
 * @return {number[]}
 */

题目给我们一个二叉树的根节点 root

要求我们寻找二叉树从右边观看的时候能看到的节点元素值，并且将其放入数组中返回

解题思路

本题的核心思路是，当我们遍历到新的一层的时候，要把该层最右边的节点放入数组

遍历的方法可以用 DFS 与 BFS，我们使用 DFS 进行 根节点 -> 右子树 -> 左子树 的顺序遍历

此外，我们用一个 maxHeight 变量来记录当前我们达到的最深的层

如果当前遍历的层数大于 maxHeight，我们认为到了一个新的层，此时我们把当前元素入栈（因为遍历顺序保证了当前元素必定是当前层最右边的元素）

Javascript

/**
 * 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 []
    }
    const res = []
    let maxHeight = 0

    const dfs = (node, height) => {
        if (!node) {
            return
        }
        if (height > maxHeight) {
            res.push(node.val)
            maxHeight = height
        }

        dfs(node.right, height + 1)
        dfs(node.left, height + 1)
    }

    dfs(root, 1)

    return res
};