513.找树左下角的值,112. 路径总和 113.路径总和ii, 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构

简介: 本内容涵盖了三道与二叉树相关的算法题及其解决方案。第一题“找树左下角的值”通过深度优先搜索(DFS)找到二叉树最底层最左边的节点值。第二题“路径总和”判断是否存在从根到叶子节点的路径,其节点值之和等于目标值。第三题“从中序与后序遍历序列构造二叉树”利用中序和后序遍历结果还原二叉树结构。每个题解均采用递归方法实现,逻辑清晰且高效,适用于处理大规模数据的二叉树问题。

 题目:513. 找树左下角的值

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

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

示例 1:

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

输出: 1

示例 2:

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

输出: 7

提示:

二叉树的节点个数的范围是 [1,104]

-231 <= Node.val <= 231 - 1  

题解:

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == NULL && root->right == NULL) {
            if (depth > maxDepth) {
                maxDepth = depth;
                result = root->val;
            }
            return;
        }
        if (root->left) {
            depth++;
            traversal(root->left, depth);
            depth--; // 回溯
        }
        if (root->right) {
            depth++;
            traversal(root->right, depth);
            depth--; // 回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

题目:112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点。

示例 1:

输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

输出:true

解释:等于目标和的根节点到叶节点路径如上图所示。

示例 2:

输入:root = [1,2,3], targetSum = 5

输出:false

解释:树中存在两条根节点到叶子节点的路径:

(1 --> 2): 和为 3

(1 --> 3): 和为 4

不存在 sum = 5 的根节点到叶子节点的路径。

示例 3:

输入:root = [], targetSum = 0

输出:false

解释:由于树是空的,所以不存在根节点到叶子节点的路径。

提示:

树中节点的数目在范围 [0, 5000] 内

-1000 <= Node.val <= 1000

-1000 <= targetSum <= 1000

题解:

class Solution {
private:
    bool traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点,并且计数为0
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回
 
        if (cur->left) { // 左
            count -= cur->left->val; // 递归,处理节点;
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯,撤销处理结果
        }
        if (cur->right) { // 右
            count -= cur->right->val; // 递归,处理节点;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯,撤销处理结果
        }
        return false;
    }
 
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;
        return traversal(root, sum - root->val);
    }
};

题目:106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

示例 1:

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

输出:[3,9,20,null,null,15,7]

示例 2:

输入:inorder = [-1], postorder = [-1]

输出:[-1]

提示:

1 <= inorder.length <= 3000

postorder.length == inorder.length

-3000 <= inorder[i], postorder[i] <= 3000

inorder 和 postorder 都由 不同 的值组成

postorder 中每一个值都在 inorder 中

inorder 保证是树的中序遍历

postorder 保证是树的后序遍历

题解:

class Solution {
private:
    TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;
 
        // 后序遍历数组最后一个元素,就是当前的中间节点
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);
 
        // 叶子节点
        if (postorder.size() == 1) return root;
 
        // 找到中序遍历的切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
 
        // 切割中序数组
        // 左闭右开区间:[0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        // [delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
 
        // postorder 舍弃末尾元素
        postorder.resize(postorder.size() - 1);
 
        // 切割后序数组
        // 依然左闭右开,注意这里使用了左中序数组大小作为切割点
        // [0, leftInorder.size)
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        // [leftInorder.size(), end)
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
 
        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);
 
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};


相关文章
|
8月前
|
测试技术 API 持续交付
【Git】实际项目中 Git 的最佳实践
本文系统总结Git在实际项目中的八大最佳实践:涵盖分支策略(Git Flow/TBD)、Conventional Commits提交规范、PR代码审查要点、核心分支保护、冲突预防与解决、敏感信息管理、高效命令技巧(stash/bisect/reflog)及团队协作规范,助力提升协作效率与代码质量。
|
10月前
|
人工智能 弹性计算 机器人
阿里云无影云电脑已上线Clawdbot(Moltbot)专属镜像,1键部署Moltbot AI 助手教程
阿里云无影云电脑已上线Moltbot(原Clawdbot)专属镜像,镜像预装VS Code、TMUX、钉钉、WPS等常用组件,支持钉钉、QQ等软件唤醒,无需复杂环境配置,3步即可部署完成。这款AI智能助理能操作文件、处理工作、联动多工具,同时打通网关与云电脑,帮助用户快速创建个人Agent。目前更多相关技能正在持续解锁,企业微信等接入能力也在加速适配中。
2552 0
|
8月前
|
存储 缓存 监控
90% 的 JVM 元空间 OOM,都栽在类加载与类卸载上!调优 + 排查全攻略
本文深入剖析JVM元空间OOM、频繁Full GC等生产问题,聚焦类加载机制、元空间内存模型与类卸载三要素,详解自定义类加载器泄漏、线程上下文类加载器未恢复等5大高频场景,提供参数调优、日志观测、MAT排查及修复实战方案。
1233 3
|
10月前
|
机器学习/深度学习 数据可视化 算法
【无人机】四旋翼无人机建模+分析+仿真可视化的matlab代码,非线性刚体动力学模型、解耦的线性传递函数模型
✅作者简介:热爱科研的Matlab仿真开发者,擅长数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。 🍎 往期回顾关注个人主页: Matlab科研工作室  👇 关注我领取海量matlab电子书和数学建模资料  🍊个人信条:格物致知, 完整Matlab代码获取 及仿真咨询内容私信。 🔥  内容介绍  一、研究背景与主题引入 四旋翼无人机凭借垂直起降、空中悬停及高机动性等特性,在航拍、物流配送、农业植保、电力巡检等领域广泛应用。其动力学系统具有强非线性、强耦合特性,且受空气动力学效应、电机动力学滞后及外界扰动(如阵风)影响显著。传统线性控制方法在复杂飞行场景中易出现超调、振荡
349 1
|
10月前
|
人工智能 供应链 搜索推荐
AI智能体是刚需还是噱头?2026年五大争议辨真相
2026年,AI智能体赛道呈现“冰火两重天”:巨头重金布局,微软、谷歌争相构建生态;明星初创却接连倒闭。技术能力、ROI、场景真伪、生态格局与安全伦理五大争议,揭示其在降本增效与成本黑洞间的艰难平衡,展现真实价值与泡沫并存的复杂图景。
|
机器学习/深度学习 Java 开发工具
【移花接木】OpenCV4.8 For Java 深度学习 实时人脸检测
【移花接木】OpenCV4.8 For Java 深度学习 实时人脸检测
533 0
|
存储 机器学习/深度学习 人工智能
日志分析软件
【10月更文挑战第18天】
2048 7
|
监控 网络架构 负载均衡
|
域名解析 开发框架 Ubuntu
Caddy VS Nginx,谁才是真正的王者
Caddy 2 is a powerful, enterprise-ready, open source web server with automatic HTTPS written in Go.
8681 1
Caddy VS Nginx,谁才是真正的王者
|
Linux
CentOS下载ISO镜像的方法
CentOS 介绍 CentOS,中文意思是社区企业操作系统是Linux发行版之一,是免费的、开源的、可以重新分发的开源操作系统。 CentOS Linux发行版是一个稳定的,可预测的,可管理的和可复现的平台,源于Red Hat Enterprise Linux(RHEL)依照开放源代码(大部分是GPL开源协议)规定释出的源码所编译而成。
4932 1