「力扣」第 199 题:二叉树的右视图(中等)


「力扣」第 199 题:二叉树的右视图(中等)

传送门:199. 二叉树的右视图

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

示例:

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

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

分析:1、深度优先遍历;2、层序遍历(2种写法,本质上其实一样)。

方法一:广度优先遍历

Java 代码:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


public class Solution {

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        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 node = queue.poll();
                if (i == 0) {
                    res.add(node.val);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
            }
        }
        return res;
    }
}

Python 代码:

from typing import List
from collections import deque


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if root is None:
            return []

        res = []
        queue = deque()
        queue.append(root)
        while queue:
            cur_size = len(queue)
            res.append(queue[-1].val)
            # 这里要注意,上一层的结点要全部出列
            for _ in range(cur_size):
                top = queue.popleft()
                if top.left:
                    queue.append(top.left)
                if top.right:
                    queue.append(top.right)
        return res

方法二:深度优先遍历

Java 代码:

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        dfs(root, 0, res);
        return res;
    }


    private void dfs(TreeNode node, int level, List<Integer> res) {
        // 如果 node 为空,就直接返回,一定要先写,以减少很多判断
        if (node == null) {
            return;
        }
        if (res.size() == level) {
            res.add(node.val);
        }
        // 如果交换下面两行的顺序,那么就得到二叉树的左视图
        dfs(node.right, level + 1, res);
        dfs(node.left, level + 1, res);
    }
}

Python 代码:

from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        def dfs(node, res, depth):
            if node is None:
                return
            if len(res) == depth:
                res.append(node.val)
            dfs(node.right, res, depth + 1)
            dfs(node.left, res, depth + 1)

        res = []
        dfs(root, res, 0)
        return res

(本节完)


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「并查集」专题 1:并查集简介 「并查集」专题 1:并查集简介
「并查集」专题 1:并查集简介重点提示 「并查集」是一种建立在「数组」上的树形结构,并且这棵树的特点是孩子结点指向父亲结点; 「并查集」主要用于解决「动态连通性」问题,重点关注的是连接问题,并不关注路径问题; 「并查集」是树,所以优化的策
下一篇 
「力扣」第 295 题:数据流的中位数(中等) 「力扣」第 295 题:数据流的中位数(中等)
「力扣」第 295 题:数据流的中位数(中等)传送门:295. 数据流的中位数。 题解地址:优先队列(Python 代码、Java 代码)。 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2, 3
  目录