长大后想做什么？做回小孩！

0%

LeetCode——二叉树的右视图

发表于 分类于 Valine：
本文字数： 270

NO.199 二叉树的右视图 中等

JtSLnA.png

思路一：层序遍历 看示例最直观的解法，层序遍历，只保存每一层的最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    if (root == null) return res;
    //层序遍历
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode poll = queue.poll();
            //只保存每层最后一个元素
            if (i == size - 1) res.add(poll.val);
            if (poll.left != null) queue.add(poll.left);
            if (poll.right != null) queue.add(poll.right);
        }
    }
    return res;
}

时间复杂度：O(n)

思路一：深度优先遍历 根据观察，每一层都保存最右边的元素，可以根据”根->右->左”的方式去进行遍历，保证优先访问到右边的节点。

记录访问节点所在的当前层的深度，如果当前层没有节点被保存，说明访问节点是本层第一次被访问到的节点，因为右边的节点优先访问，所以保存当前访问节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
List<Integer> res = new LinkedList<>();

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

private void dfs(TreeNode root, int depth) {
    if (root == null) return;
    //因为每层只会保存第一个访问到的节点。
    //所以size=depth，说明当前层第一次访问。root一定是本层最右节点。
    if (res.size() == depth) res.add(root.val);
    //右>左
    dfs(root.right, depth + 1);
    dfs(root.left, depth + 1);
}

时间复杂度：O(n)

空间：最好O(logn) 最坏退化而为链表O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github