大家好呀,我是快乐的蛋蛋。
今天解决二叉树的右视图,右视图说白了就是每一层最右面的节点,那我们怎么把它们找出来呢?
这就是今天要解决的问题,咱们话不多说,直接开始~
LeetCode 199:二叉树的右视图
题意
给定一个二叉树的根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例
输入:[1,2,3,null,5,null,4]
输出:[1,3,4]
提示
- 二叉树的节点个数的范围是 [0,100]
- -100 <= Node.val <= 100
题目解析
这道二叉树的右视图官方定级难度中等,说实话如果你是一直跟着我的题解走下来的,对你来说就是道简单题。
这个所谓的右视图,其实就是每一层最右边的那个节点,涉及到“层”的概念,我们就可以直接祭出层次遍历来解决。
如果对层次遍历不太了解的同学,可以看我下面这篇文章:
做法也很简单,对于每一层的节点从左到右遍历,保存每层最后一个遍历的节点即可。
递归法
用递归法,那还是按照往常,祭出递归二步曲:
(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。
比如对于下图:
首先初始化队列和结果 res,将根节点入队列。
# 初始化队列和结果 queue = [root] res = []
当队列不为空,节点 1 出队列,此时 node = 1 是当前层的最后一个,将节点值加入 res。
# 如果节点是当前层的最后一个,则入 res if(i == size - 1): res.append(node.val)
同时将 node = 1 的子节点入队列 queue。
// 将当前层的所有节点入队列 if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); }
之后就是重复上面的操作,不断的入队列出队列,直至队列为空。
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,都给我吹起来!
当然还要记得做好总结呦~
今天就到这了,记得帮我点赞 + 在看 + 转发一条龙呀,爱你们~
我是帅蛋,我们下次见!