当前位置: 首页 > article >正文

力扣513:找树左下角的值

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

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

层层遍历代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 #define MAX 10000
 int height(struct TreeNode *t){
    if(t==NULL) return 0;
    int heightl=height(t->left);
    int heightr=height(t->right);
    return (heightl > heightr ? heightl:heightr)+1;
 }
int findBottomLeftValue(struct TreeNode* root) {
    if(root==NULL) return 0;
    int TReeHeight=height(root);

    //利用队列进行层次遍历(BFS)
    struct TreeNode *Queue[MAX];
    struct TreeNode *temp;
    int front=0,rear=0,len=0;
    Queue[rear++]=root;
    int level=0;
    while(front<rear){
        len=rear-front;
        level++;
        for(int i=0;i<len;i++){
            if(level==TReeHeight){
                return Queue[front]->val;
            }
        temp=Queue[front++];
        if(temp->left!=NULL) Queue[rear++]=temp->left;
        if(temp->right!=NULL) Queue[rear++]=temp->right;
        }
        
    }
    return 0;
}

递归代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 int depth;
 int temp;
 void DFS(struct TreeNode *root,int h){
    if(root==NULL) return;
    DFS(root->left,h+1);
    if(h>depth){
        depth=h;
        temp=root->val;
    }
    DFS(root->right,h+1);

 }
int findBottomLeftValue(struct TreeNode* root) {
    depth=-1,temp=0;
    DFS(root,1);
    return temp;
}


http://www.kler.cn/a/394900.html

相关文章:

  • MySQL【三】
  • 修改数据库和表的字符集
  • react-redux useSelector钩子 学习样例 + 详细解析
  • Rocky、Almalinux、CentOS、Ubuntu和Debian系统初始化脚本v9版
  • ios swift开发--ios远程推送通知配置
  • 简单叙述 Spring Boot 启动过程
  • A030-基于Spring boot的公司资产网站设计与实现
  • 单片机和FPGA有什么区别?
  • PCL 点云分割 Ransac分割3D球体
  • ubuntu更改max_map_count
  • jmeter常用配置元件介绍总结之定时器
  • 基于微信小程序的养老院管理系统的设计与实现,LW+源码+讲解
  • Ubuntu 24.04 安装 JDK 21
  • 【NLP】使用 PyTorch 从头构建自己的大型语言模型 (LLM)
  • 【ChatGPT】 让ChatGPT模拟客户服务对话与应答策略
  • 使用docker-compose单点搭建社区版seafile+onlyoffice在线word编辑平台
  • 【FreeRL】MAPPO的简单复现
  • 《基于Oracle的SQL优化》读书笔记
  • Scrapy并发请求深度解析:如何高效控制爬虫速度
  • spring boot 集成 redis 实现缓存的完整的例子
  • D68【python 接口自动化学习】- python基础之数据库
  • Java 实现鼠标单击右键弹出菜单项
  • 【vue3中el-table表格高度自适应】
  • 探索 HTML 和 CSS 实现的 3D旋转相册
  • SQL面试题——蚂蚁SQL面试题 连续3天减少碳排放量不低于100的用户
  • c++写一个死锁并且自己解锁