二叉树的右视图

199. 二叉树的右视图

第一种解法，层序遍历。从右往左依次进入队列，在出队后判断一下是否为当前层第一个节点，如果是，就将节点值收集起来。

const rightSideView = function(root) {
    if (root === null) return [];
    let res = [];
    let queue = [];

    queue.push(root);
    while (queue.length > 0) {
        let size = queue.length;
        let i = size;

        while (i > 0) {
            let node = queue.shift();
            if (i === size) {
                // i 和 size 相等
                // 说明是当前层第一个节点，即最右边的节点
                res.push(node.val);
            }
            if (node.right !== null) {
                queue.push(node.right);
            }
            if (node.left != null) {
                queue.push(node.left);
            }
            i--;
        }
    }

    return res;
};

因为最终都会遍历一遍树，所以进队顺序是从左到右还是从右到左都无所谓，只要将该层最右边的节点入队即可。

var rightSideView = function(root) {
    if (root === null) return [];
    let res = [];
    let queue = [];
    queue.push(root);
    while (queue.length > 0) {
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
            if (i === size - 1) res.push(node.val);
        }
    }
    return res;
};

时间复杂度：O(n)，遍历了一遍树
空间复杂度：O(n/2 + 1)，队列最多存放最后一层节点

第二种解法是递归，遍历顺序是根右左，先遍历右孩子。题目隐藏了一个信息，那就是无论只看左边还是只看右边，一定能看清树的高度，结果数组的长度就是树的高度。利用这一信息，我们可以判断当前节点的深度和结果数组的长度，如果深度大于长度，说明这一层还没有收集，于是将当前节点放入结果数组，因为先遍历的是右孩子，所以一定是右视图看到的节点。

var rightSideView = function(root) {
    let res = [];
    dfs(root, 1, res);
    return res;
};

function dfs(root, depth, res) {
    if (root === null) return;
    // 深度大于结果数组长度，说明还没探查到这一层，
    // 因为先遍历的是右孩子，所以当前节点一定是右视图的节点
    if (res.length < depth) {
        res.push(root.val);
    }
    dfs(root.right, depth + 1, res);
    dfs(root.left, depth + 1, res);
}