ACM 选手图解 LeetCode 二叉树的右视图

简介: ACM 选手图解 LeetCode 二叉树的右视图

大家好呀,我是快乐的蛋蛋。


今天解决二叉树的右视图,右视图说白了就是每一层最右面的节点,那我们怎么把它们找出来呢?


这就是今天要解决的问题,咱们话不多说,直接开始~

640.png



 LeetCode 199:二叉树的右视图


题意


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


示例


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

输出:[1,3,4]

640.png


提示


  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100


题目解析


这道二叉树的右视图官方定级难度中等,说实话如果你是一直跟着我的题解走下来的,对你来说就是道简单题。


这个所谓的右视图,其实就是每一层最右边的那个节点,涉及到“层”的概念,我们就可以直接祭出层次遍历来解决。


如果对层次遍历不太了解的同学,可以看我下面这篇文章:


ACM 选手带你玩转二叉树层次遍历(递归 + 非递归)


做法也很简单,对于每一层的节点从左到右遍历,保存每层最后一个遍历的节点即可。

640.png


递归法


递归法,那还是按照往常,祭出递归二步曲:


(1) 找出重复的子问题。


层次遍历对于每一层,我们都是从左到右遍历,这次我们换个方向,从右向左遍历。


这样对于每一层来说,遍历的第一个节点就是。


所以在遍历的时候我们可以先遍历右子树,再遍历左子树

# 如果当前节点的深度还没出现在 res 中(因为一层就一个节点)
# 那说明当前节点是该层第一个被访问的节点,将当前节点的值加入 res
if len(res) < depth:
    res.append(root.val)
# 遍历右子树
if root.right:
    self.level(root.right, depth + 1, res)
# 遍历左子树
if root.left:
    self.level(root.left, depth + 1, res)


(2) 确定终止条件。


对于二叉树的遍历来说,想终止,即没东西遍历了,没东西遍历自然就停下来了。


即最下面一层的左右节点都为空了。

if root == None:
    return []

最重要的两点确定好了,代码也就出来了。


Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def level(self, root:TreeNode, depth, res):
        if root == None:
            return []
        # 如果当前节点的深度还没出现在 res 中(因为一层就一个节点)
        # 那说明当前节点是该层第一个被访问的节点,将当前节点的值加入 res
        if len(res) < depth:
            res.append(root.val)
        # 遍历右子树
        if root.right:
            self.level(root.right, depth + 1, res)
        # 遍历左子树
        if root.left:
            self.level(root.left, depth + 1, res)
    def rightSideView(self, root: TreeNode) -> List[int]:
        res = []
        self.level(root, 1, res)
        return res


Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    void level(TreeNode root, int depth, List<Integer> res){
        // 如果当前节点的深度还没出现在 res 中(因为一层就一个节点)
        // 那说明当前节点是该层第一个被访问的节点,将当前节点的值加入 res
        if(res.size() < depth){
            res.add(root.val);
        }
        // 遍历右子树
        if(root.right != null){
            level(root.right, depth + 1, res);
        }
        // 遍历左子树
        if(root.left != null){
            level(root.left, depth + 1, res);
        }
    }
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            return new ArrayList<Integer>();
        }
        List<Integer> res = new ArrayList<Integer>();
        level(root, 1, res);
        return res;
    }
}


本题解,在递归过程中每个节点都被遍历到,时间复杂度为 O(n)


此外在递归过程中调用了额外的栈空间,栈的大小取决于二叉树的高度,二叉树最坏情况下的高度为 n,所以空间复杂度为 O(n)


非递归法(迭代)


非递归版的层次遍历用的则是队列,这是由于层次遍历的属性非常契合队列的特点。


具体做法就是:使用队列保存每一层的所有节点,把队列里的所有节点出队列,如果当前节点是当前层的最后一个,入 res。


比如对于下图:

640.png



首先初始化队列和结果 res,将根节点入队列。

640.png

# 初始化队列和结果
queue = [root]
res = []


当队列不为空,节点 1 出队列,此时 node = 1 是当前层的最后一个,将节点值加入 res。

640.png

# 如果节点是当前层的最后一个,则入 res
if(i == size - 1):
    res.append(node.val)


同时将 node = 1 的子节点入队列 queue。

640.png

// 将当前层的所有节点入队列
if(node.left != null){
    queue.offer(node.left);
}
if(node.right != null){
    queue.offer(node.right);
}

之后就是重复上面的操作,不断的入队列出队列,直至队列为空。


640.png



Python 代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if root == None:
            return []
        # 初始化队列和结果
        queue = [root]
        res = []
        # 当队列不为空
        while queue:
            # 当前层的节点数
            size = len(queue)
            # 弹出当前层的所有节点
            for i in range(size):
                node = queue.pop(0)
                # 如果节点是当前层的最后一个,则入 res
                if(i == size - 1):
                    res.append(node.val)
                # 将当前层的所有节点入队列
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return res


Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if(root == null){
            return new ArrayList<Integer>();
        }
        // 初始化队列和结果
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<Integer> res = new ArrayList<Integer>();
        // 当队列不为空
        while(!queue.isEmpty()){
            // 当前层的节点数
            int size = queue.size();
            // 弹出当前层的所有节点
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                // 如果节点是当前层的最后一个,则入 res
                if(i == size - 1){
                    res.add(node.val);
                }
                // 将当前层的所有节点入队列
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
        }
        return res;
    }
}


本题解,对于每个节点,各进出队列一次,所以时间复杂度为 O(n)


此外,额外维护了一个队列,所以空间复杂度为 O(n)



图解二叉树的右视图到这就结束辣,层次遍历 YYDS,都给我吹起来!


当然还要记得做好总结呦~


今天就到这了,记得帮我点赞 + 在看 + 转发一条龙呀,爱你们~


我是帅蛋,我们下次见!

相关文章
|
1月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
19 2
|
1月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
15 2
|
1月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
15 2
|
1月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
18 0
|
1月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
14 0
|
1月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
16 0
|
1月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
12 0
|
1月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
16 0
|
3月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
|
3月前
|
算法 Java
LeetCode第94题二叉树的中序遍历
文章介绍了LeetCode第94题"二叉树的中序遍历"的解法,使用递归实现了中序遍历的过程,遵循了"左根右"的遍历顺序,并提供了清晰的Java代码实现。
LeetCode第94题二叉树的中序遍历