leetcode 199. 二叉树的右视图(层序遍历的应用)
给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
题解:
1.一棵二叉树
2.按从顶部到底部的顺序
3.返回从右侧看到的值
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <---
/ \
2 3 <---
\ \
5 4 <---
解题思路:
-
既然是从右边看到的数值,也就是看到的是每层结点的最后一个数值
-
考虑实现层序遍历,把每层最后一个元素添加到结果集中
-
同样如果是左视图就把每层第一个元素添加到结果集中
-
二叉树的层序遍历使用队列实现
C/C++题解:(前往底部公众号回复“199”免费获取)
/*** Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* }; */
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
Java题解:(前往底部公众号回复“199”免费获取)
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Python题解:(前往底部公众号回复“199”免费获取)
class Solution(object):
def rightSideView(self, root):
""":type root: TreeNode:rtype: List[int]"""
例题来自力扣网https://leetcode-cn.com/
更多题解可前往公众号免费获取
C++ queue常用成员函数:
front():返回 queue 中第一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
back():返回 queue 中最后一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。
push(const T& obj):在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
push(T&& obj):以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
pop():删除 queue 中的第一个元素。
size():返回 queue 中元素的个数。
empty():如果 queue 中没有元素的话,返回 true。
emplace():用传给 emplace() 的参数调用 T 的构造函数,在 queue 的尾部生成对象。
swap(queue<T> &other_q):将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。
Java Queue类常用成员函数:
在Java中经常使用LinkedList类来实现Queue队列
boolean add(E e) //将指定的元素插入此队列(如果立即可行且不会违反容量限制),在成功时返回 true,如果当前没有可用的空间,则抛出 IllegalStateException。
E element() //获取,但是不移除此队列的头。
boolean offer(E e) //将指定的元素插入此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。
E peek() //获取但不移除此队列的头;如果此队列为空,则返回 null。
E poll() //获取并移除此队列的头,如果此队列为空,则返回 null。
E remove() //获取并移除此队列的头。