leetcode199(二叉树的右视图)–Java语言实现

求：

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

示例:

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

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

题目链接： https://leetcode-cn.com/problems/binary-tree-right-side-view/ https://leetcode-cn.com/problems/binary-tree-right-side-view/

解：

1、广度优先遍历（BFS）

这题最自然的想到使用BFS，使用一个队列记录每一层的遍历结果，并记录每一层最后一个遍历到的节点的值到一个动态的List中，最后返回这个List。

时间复杂度：O(N)

空间复杂度：O(N)

public List<Integer> rightSideView(TreeNode root) {
    List<Integer> retList = new LinkedList<>();
    if (root == null) return retList;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        TreeNode t = null;
        for (int i = 0; i < size; i++) {
            t = q.poll();
            if (t.left != null) q.offer(t.left);
            if (t.right != null) q.offer(t.right);
        }
        retList.add(t.val);
    }
    return retList;
}

2、深度优先遍历（DFS）

先序递归遍历，同一深度的节点可能有多个，对相同深度的所有节点，只加入第一个遍历到的节点的值到List，最后返回List。

时间复杂度：O(N)

空间复杂度：O(N)

private List<Integer> retList = new LinkedList<>();

public List<Integer> rightSideView(TreeNode root) {
    Traverse(root, 0);
    return retList;
}

private void Traverse(TreeNode root, Integer thisDepth) {
    if (root == null) return;
    if (++thisDepth > retList.size()) retList.add(root.val);
    Traverse(root.right, thisDepth);
    Traverse(root.left, thisDepth);
}