Pengjielee's blog

题目

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/binary-tree-right-side-view 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JS实现

1、BFS

利用BFS进行层次遍历，记录下每层的最后一个元素。

/**
 * 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) {
  const result = [];

  if (root === null) {
    return result;
  }

  //队列特点：先进先出
  const q = [];
  //入队根节点
  q.push(root);

  while (q.length) {
    //每一层的结果
    const level = [];
    //队列的长度
    const len = q.length;
    //遍历队列
    for (let i = 0; i < len; i++) {
      const node = q.shift();
      //保存这一层的节点 
      level.push(node.val);

      //入队下一层的左节点
      if (node.left) {
        q.push(node.left);
      }
      //入队下一层的右节点
      if (node.right) {
        q.push(node.right);
      }
    }

    //保存每一层的最右边的节点
    result.push(level[level.length - 1]);
  }

  return result;
};

2、DFS

思路：我们按照「根结点 -> 右子树 -> 左子树」的顺序访问，就可以保证每层都是最先访问最右边的节点的。

（与先序遍历「根结点 -> 左子树 -> 右子树」正好相反，先序遍历每层最先访问的是最左边的节点）

作者：sweetiee 链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/jian-dan-bfsdfs-bi-xu-miao-dong-by-sweetiee/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

var rightSideView = function (root) {
  const result = [];

  const dfs = (root, depth) => {
    if (root === null) {
      return;
    }
    // 先访问 当前节点，再递归地访问 右子树 和 左子树。
    // 如果当前节点所在深度还没有出现在result里，
    // 说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入result中。
    if (depth === result.length) {
      result.push(root.val);
    }
    depth++;
    dfs(root.right, depth);
    dfs(root.left, depth);
  };

  //从根节点开始访问，根节点深度是0
  dfs(root, 0);

  return result;
};

Go实现

package main

import (
  "fmt"
)

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

func main() {
  root := &TreeNode{
    Val:   1,
    Left:  &TreeNode{Val: 2},
    Right: &TreeNode{Val: 3},
  }
  fmt.Println(rightSideView(root))
}

func rightSideView(root *TreeNode) []int {
  res := []int{}
  if root == nil {
    return res
  }
  //声明一个队列，并添加根节点
  queue := []*TreeNode{root}
  for len(queue) > 0 {
    n := len(queue)
    for i := 0; i < n; i++ {
      if queue[i].Left != nil {
        queue = append(queue, queue[i].Left)
      }
      if queue[i].Right != nil {
        queue = append(queue, queue[i].Right)
      }
    }
    //添加队列最右边的元素
    res = append(res, queue[n-1].Val)
    //出队
    queue = queue[n:]
  }
  return res
}