首页 > 其他分享 >(LeetCode 热题 100) 199. 二叉树的右视图(递归、深度优先搜索dfs)

(LeetCode 热题 100) 199. 二叉树的右视图(递归、深度优先搜索dfs)

时间:2024-09-21 12:54:35浏览次数:7  
标签:right TreeNode nullptr visit dfs 视图 二叉树 root left

199. 二叉树的右视图

在这里插入图片描述
在这里插入图片描述

思路:递归每次都优先右边子树,然后才是左子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
	//root:当前根节点、d:当前深度
    void dfs(TreeNode* root,int d,vector<int> & depth,vector<int> & visit){
        //为空直接返回
        if(root==nullptr) return;
        //当前深度第一次出现
        if(!depth[d]){
            depth[d]=1;
            visit.push_back(root->val);
        }
        //右子树
        dfs(root->right,d+1,depth,visit);
        //左子树
        dfs(root->left,d+1,depth,visit);
    }
    vector<int> rightSideView(TreeNode* root) {
    	//记录每个深度是否已有节点被看见
        vector<int> depth(105,0);
        vector<int> visit;//记录被看见的节点
        //递归
        dfs(root,0,depth,visit);
        return visit;
    }
};

优化一下空间。每次插入节点值时,其实都是遇见了一个新的深度,即:visit.size()==d。因此不需要数组depth。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root,int d,vector<int> & visit){
        if(root==nullptr) return;
        //优化
        if(visit.size()==d){
            visit.push_back(root->val);
        }
        dfs(root->right,d+1,visit);
        dfs(root->left,d+1,visit);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector<int> visit;
        dfs(root,0,visit);
        return visit;
    }
};

标签:right,TreeNode,nullptr,visit,dfs,视图,二叉树,root,left
From: https://blog.csdn.net/weixin_46028214/article/details/142414589

相关文章

  • 数据结构:二叉树(2)
    ps:爆更第二期前言普通的树的实用价值比较小,将树更一步特殊化成二叉树,将获得更多的特殊性质。例如搜索二叉树,红黑树等。这篇博文主要介绍二叉树的基础知识,进阶版高级二叉树,后续会持续更新。二叉树的概念一棵二叉树是结点的一个有限集合,该集合:或者为空由一个根节点......
  • 【C++二叉树】105.从前序与中序遍历序列构造二叉树
    105.从前序与中序遍历序列构造二叉树-力扣(LeetCode)根据前序遍历和中序遍历构建二叉树前序遍历访问方式:根-左子树-右子树中序遍历访问方式:左子树-根-右子树思路分析:前序+中序可以构建一颗二叉树:前序遍历可以确定根,中序遍历可以确定左子树的中序区间和右子树的中序区......
  • 代码随想录算法训练营第十五天 | Javascript | 继续二叉树的一天 | 力扣Leetcode | 补
    目录前言简介题目链接:501.二叉搜索树中的众数题目链接:236.二叉树的最近公共祖先题目链接:235.二叉搜索树的最近公共祖先前言踏平坎坷成大道,斗罢艰险又出发!自律的尽头是自控,自控的尽头是硬控。愿道友们披荆斩棘,终能得偿所愿。简介本人是小几年经验的前端开发,......
  • 代码随想录 -- 二叉树 -- 把二叉搜索树转换为累加树
    538.把二叉搜索树转换为累加树-力扣(LeetCode)思路:定义pre变量用来记录当前节点的前一个节点(右中左顺序遍历)的值。递归出口:当root为空时,return。单层递归逻辑:(右中左)右:self.tra(root.right)中:令root的值为它本身加上pre,更新pre为当前root的值;左:self.tra(root.left)class......
  • 代码随想录 -- 二叉树 -- 将有序数组转换为二叉搜索树
    108.将有序数组转换为二叉搜索树-力扣(LeetCode)思路:(注意题目要求是平衡二叉树!!!)递归出口:当传入数组为空时,返回空。单层递归逻辑:找到数组中间的值,令其为root,数组左边为root的左子树,数组右边为root的右子树。最后返回root。classSolution(object):defsortedArrayTo......
  • 代码随想录 -- 二叉树 -- 修剪二叉搜索树
     669.修剪二叉搜索树-力扣(LeetCode)思路:递归出口:当root为空时,返回空。当root的值比low小时,如果root没有右子树,直接返回空;否则返回trimBST(root.right,low,high)。当root的值比high大时,如果root没有左子树,直接返回空;否则返回trimBST(root.left,low,high)。单层递归逻辑:......
  • 11 UML中的逻辑视图、进程视图、实现视图、部署视图
    UML(UnifiedModelingLanguage,统一建模语言)是一种用于对软件密集系统进行可视化建模的标准语言。在UML中,系统可以从不同的角度进行描述,这些不同的角度被称为视图。具体来说,UML中的逻辑视图、进程视图、实现视图和部署视图分别代表了系统的不同方面。1.逻辑视图(LogicalView)定义......
  • DevExpress WinForms中文教程:Data Grid - 如何设置视图和列外观?
    本教程将带您了解用于更改网格元素外观的外观设置,在哪里可以找到视图或单个列的这些设置,以及如何更改视图的绘制样式,以便您可以自定义主题绘制的元素。P.S:DevExpressWinForms拥有180+组件和UI库,能为WindowsForms平台创建具有影响力的业务解决方案。DevExpressWinForms能完美构......
  • 计算机组成与体系结构——计算机功能和互连地顶层视图
    计算机的部件几乎所有的当代计算机设计都是以冯·诺依曼提出的概念为基础的,它基于以下三个概念:数据和指令存储在单一的读/写存储器中存储器的内容通过位置寻址,而不关心存储在其中的数据类型从一条指令到下一条指令(除非显示修改)顺序执行。一种方式是硬连线程序(HardwiredP......
  • 代码随想录刷题day13 | LeetCode 110.平衡二叉树 257. 二叉树的所有路径 404.左叶子之
    110.平衡二叉树力扣题目链接后序遍历求高度,高度判断是否平衡|LeetCode:110.平衡二叉树1.三元运算符:(?:)condition?expression_if_true:expression_if_false;前面是条件,如果符合就等于冒号前的expression_if_true,反之则是后面的。2.如果要使用if(!node->left),要......