上海电商网站建设费用,佳木斯建网站的,泰州网站优化公司,百度交易平台原题链接#x1f517;#xff1a;二叉树的右视图 难度#xff1a;中等⭐️⭐️
题目
给定一个二叉树的 根节点 root#xff0c;想象自己站在它的右侧#xff0c;按照从顶部到底部的顺序#xff0c;返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4…原题链接二叉树的右视图 难度中等⭐️⭐️
题目
给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2:
输入: [1,null,3] 输出: [1,3]
示例 3:
输入: [] 输出: []
提示:
二叉树的节点个数的范围是 [0,100]-100 Node.val 100
题解
二叉树
二叉树是一种基本的树形数据结构其中每个节点最多有两个子节点通常称为左子节点和右子节点。二叉树的特点是每个节点的左子节点的值小于或等于该节点的值而右子节点的值大于或等于该节点的值。这种特性使得二叉树非常适合用于排序和搜索操作。
二叉树右视图
二叉树的右视图问题通常指的是从二叉树的右侧观察获取从上到下每一层最右边的节点值。这个问题可以通过广度优先搜索BFS算法来解决因为BFS可以按层序遍历二叉树。
广度优先搜索法
解题思路 LeetCode 上的题目 “二叉树的右视图” 要求我们从二叉树的右侧观察打印出每一层的最后一个节点的值。这个问题可以通过多种方法解决但最常用的是使用广度优先搜索BFS算法。执行广度优先搜索左结点排在右结点之前这样我们对每一层都从左到右访问。因此只保留每个深度最后访问的结点我们就可以在遍历完整棵树后得到每个深度最右的结点。 以下是解题思路的步骤 理解问题首先明确题目要求我们打印出二叉树每层的最后一个节点的值。 使用队列由于我们需要逐层访问节点队列是实现这一目标的理想数据结构。 初始化 创建一个队列 queue 来存储当前层的节点。创建一个列表 result 来存储每层的最后一个节点的值。 BFS 遍历 将根节点加入队列。当队列不为空时进行循环 记录当前层的节点数量例如 level_size。迭代 level_size 次每次从队列中取出一个节点 如果是当前层的最后一个节点即 queue 中没有其他节点则将其值添加到 result 中。将当前节点的右子节点如果有的话加入队列。如果当前节点有左子节点先将其加入队列然后再处理右子节点以确保右视图的顺序。 返回结果遍历结束后result 列表将包含每层的最后一个节点的值返回这个列表。 注意在处理节点时如果节点为 None则忽略它。 代码实现根据上述思路使用适当的编程语言实现算法。 复杂度时间复杂度为空间复杂度为。c demo
#include iostream
#include vector
#include queue// 定义二叉树的节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:// 函数用于获取二叉树的右视图std::vectorint rightSideView(TreeNode* root) {std::vectorint result;if (!root) return result;std::queueTreeNode* q;q.push(root);while (!q.empty()) {int levelSize q.size(); // 当前层的节点数量for (int i 0; i levelSize; i) {TreeNode* node q.front();q.pop();// 如果是当前层的最后一个节点添加到结果中if (i levelSize - 1) {result.push_back(node-val);}// 将左子节点入队如果有的话if (node-left) q.push(node-left);// 将右子节点入队如果有的话if (node-right) q.push(node-right);}}return result;}
};int main() {// 创建一个示例二叉树// 1// / \// 2 3// / \ \// 4 5 6TreeNode* root new TreeNode(1);root-left new TreeNode(2);root-right new TreeNode(3);root-left-left new TreeNode(4);root-left-right new TreeNode(5);root-right-right new TreeNode(6);Solution solution;std::vectorint rightView solution.rightSideView(root);// 打印右视图结果for (int val : rightView) {std::cout val ;}std::cout std::endl;// 释放二叉树内存这里简化了释放过程实际中需要递归释放所有节点delete root-left-left;delete root-left-right;delete root-left;delete root-right-right;delete root-right;delete root;return 0;
}输出结果 1 3 6 代码仓库地址rightSideView
