代码随想录阅读笔记-二叉树【二叉树的所有路径】

题目

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例: 

257.二叉树的所有路径1

思路 

这道题目要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径。

在这道题目中将第一次涉及到回溯,因为我们要把路径记录下来,需要回溯来回退一个路径再进入另一个路径。

前序遍历以及回溯的过程如图:

257.二叉树的所有路径

我们先使用递归的方式,来做前序遍历。要知道递归和回溯就是一家的,本题也需要回溯。

递归

1、递归函数参数以及返回值

要传入根节点,记录每一条路径的path,和存放结果集的result,这里递归不需要返回值。

void traversal(TreeNode* cur, vector<int>& path, vector<string>& result)

2、确定递归终止条件

在写递归的时候都习惯了这么写:

if (cur == NULL) {
    终止处理逻辑
}

但是本题的终止条件这样写会很麻烦,因为本题要找到叶子节点,就开始结束的处理逻辑了(把路径放进result里)。那么什么时候算是找到了叶子节点? 是当 cur不为空,其左右孩子都为空的时候,就找到叶子节点。

所以本题的终止条件是:

if (cur->left == NULL && cur->right == NULL) {
    终止处理逻辑
}

为什么没有判断cur是否为空呢,因为下面的逻辑可以控制空节点不入循环。

再来看一下终止处理的逻辑。

这里使用vector 结构path来记录路径,所以要把vector 结构的path转为string格式,再把这个string 放进 result里。

那么为什么使用了vector 结构来记录路径呢? 因为在下面处理单层递归逻辑的时候,要做回溯,使用vector方便来做回溯。

可能有的同学问了,我看有些人的代码也没有回溯啊。

其实是有回溯的,只不过隐藏在函数调用时的参数赋值里,下文我还会提到。

这里我们先使用vector结构的path容器来记录路径,那么终止处理逻辑如下:

if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点
    string sPath;
    for (int i = 0; i < path.size() - 1; i++) { // 将path里记录的路径转为string格式
        sPath += to_string(path[i]);
        sPath += "->";
    }
    sPath += to_string(path[path.size() - 1]); // 记录最后一个节点(叶子节点)
    result.push_back(sPath); // 收集一个路径
    return;
}

3、确定单层递归逻辑

因为是前序遍历,需要先处理中间节点,中间节点就是我们要记录路径上的节点,先放进path中。

path.push_back(cur->val);

然后是递归和回溯的过程,上面说过没有判断cur是否为空,那么在这里递归的时候,如果为空就不进行下一层递归了。

所以递归前要加上判断语句,下面要递归的节点是否为空,如下

if (cur->left) {
    traversal(cur->left, path, result);
}
if (cur->right) {
    traversal(cur->right, path, result);
}

此时还没完,递归完,要做回溯啊,因为path 不能一直加入节点,它还要删节点,然后才能加入新的节点。那么回溯要怎么回溯呢,一些同学会这么写,如下:

if (cur->left) {
    traversal(cur->left, path, result);
}
if (cur->right) {
    traversal(cur->right, path, result);
}
path.pop_back();

这个回溯就有很大的问题,我们知道,回溯和递归是一一对应的,有一个递归,就要有一个回溯,这么写的话相当于把递归和回溯拆开了, 一个在花括号里,一个在花括号外。

所以回溯要和递归永远在一起,世界上最遥远的距离是你在花括号里,而我在花括号外!

那么代码应该这么写:

if (cur->left) {
    traversal(cur->left, path, result);
    path.pop_back(); // 回溯
}
if (cur->right) {
    traversal(cur->right, path, result);
    path.pop_back(); // 回溯
}

那么本题整体代码如下:

// 版本一
class Solution {
private:

    void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
        path.push_back(cur->val); // 中,中为什么写在这里,因为最后一个节点也要加入到path中 
        // 这才到了叶子节点
        if (cur->left == NULL && cur->right == NULL) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            result.push_back(sPath);
            return;
        }
        if (cur->left) { // 左 
            traversal(cur->left, path, result);
            path.pop_back(); // 回溯
        }
        if (cur->right) { // 右
            traversal(cur->right, path, result);
            path.pop_back(); // 回溯
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};

如上的C++代码充分体现了回溯。

那么如上代码可以精简成如下代码:

class Solution {
private:

    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左
        if (cur->right) traversal(cur->right, path + "->", result); // 右
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;

    }
};

如上代码精简了不少,也隐藏了不少东西。

注意在函数定义的时候void traversal(TreeNode* cur, string path, vector<string>& result) ,定义的是string path,每次都是复制赋值,不用使用引用,否则就无法做到回溯的效果。(这里涉及到C++语法知识)

那么在如上代码中,貌似没有看到回溯的逻辑,其实不然,回溯就隐藏在traversal(cur->left, path + "->", result);中的 path + "->" 每次函数调用完,path依然是没有加上"->" 的,这就是回溯了。

为了把这份精简代码的回溯过程展现出来,大家可以试一试把:

if (cur->left) traversal(cur->left, path + "->", result); // 左  回溯就隐藏在这里

改成如下代码:

path += "->";
traversal(cur->left, path, result); // 左

即:

if (cur->left) {
    path += "->";
    traversal(cur->left, path, result); // 左
}
if (cur->right) {
    path += "->";
    traversal(cur->right, path, result); // 右
}

此时就没有回溯了,这个代码就是通过不了的了。

如果想把回溯加上,就要 在上面代码的基础上,加上回溯,就可以AC了。

if (cur->left) {
    path += "->";
    traversal(cur->left, path, result); // 左
    path.pop_back(); // 回溯 '>'
    path.pop_back(); // 回溯 '-'
}
if (cur->right) {
    path += "->";
    traversal(cur->right, path, result); // 右
    path.pop_back(); // 回溯 '>' 
    path.pop_back(); //  回溯 '-' 
}

整体代码如下:

//版本二
class Solution {
private:
    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中,中为什么写在这里,因为最后一个节点也要加入到path中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) {
            path += "->";
            traversal(cur->left, path, result); // 左
            path.pop_back(); // 回溯 '>'
            path.pop_back(); // 回溯 '-'
        }
        if (cur->right) {
            path += "->";
            traversal(cur->right, path, result); // 右
            path.pop_back(); // 回溯'>'
            path.pop_back(); // 回溯 '-'
        }
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;

    }
};

大家应该可以感受出来,如果把 path + "->"作为函数参数就是可以的,因为并没有改变path的数值,执行完递归函数之后,path依然是之前的数值(相当于回溯了)

综合以上,第二种递归的代码虽然精简但把很多重要的点隐藏在了代码细节里,第一种递归写法虽然代码多一些,但是把每一个逻辑处理都完整的展现出来了。

拓展

这里讲解本题解的写法逻辑以及一些更具体的细节

在第二版本的代码中,其实仅仅是回溯了 -> 部分(调用两次pop_back,一个pop> 一次pop-),大家应该疑惑那么 path += to_string(cur->val); 这一步为什么没有回溯呢? 一条路径能持续加节点 不做回溯吗?

其实关键还在于 参数,使用的是 string path,这里并没有加上引用& ,即本层递归中,path + 该节点数值,但该层递归结束,上一层path的数值并不会受到任何影响。 如图所示:

节点4 的path,在遍历到节点3,path+3,遍历节点3的递归结束之后,返回节点4(回溯的过程),path并不会把3加上。

所以这是参数中,不带引用,不做地址拷贝,只做内容拷贝的效果。(这里涉及到C++引用方面的知识)

在第一个版本中,函数参数我就使用了引用,即 vector<int>& path ,这是会拷贝地址的,所以 本层递归逻辑如果有path.push_back(cur->val); 就一定要有对应的 path.pop_back()

那有同学可能想,为什么不去定义一个 string& path 这样的函数参数呢,然后也可能在递归函数中展现回溯的过程,但关键在于,path += to_string(cur->val); 每次是加上一个数字,这个数字如果是个位数,那好说,就调用一次path.pop_back(),但如果是 十位数,百位数,千位数呢? 百位数就要调用三次path.pop_back(),才能实现对应的回溯操作,这样代码实现就太冗余了。

所以,第一个代码版本中,我才使用 vector 类型的path,这样方便给大家演示代码中回溯的操作。 vector类型的path,不管 每次 路径收集的数字是几位数,总之一定是int,所以就一次 pop_back就可以。

迭代法

至于非递归的方式,我们可以依然可以使用前序遍历的迭代方式来模拟遍历路径的过程,对该迭代方式不了解的同学,可以看之前关于二叉树迭代遍历的博客,我们一般是使用栈或者队列模拟二叉树的遍历和操作,这里除了模拟递归需要一个栈,同时还需要一个栈来存放对应的遍历路径。

C++代码如下:

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        stack<TreeNode*> treeSt;// 保存树的遍历节点
        stack<string> pathSt;   // 保存遍历路径的节点
        vector<string> result;  // 保存最终路径集合
        if (root == NULL) return result;
        treeSt.push(root);
        pathSt.push(to_string(root->val));
        while (!treeSt.empty()) {
            TreeNode* node = treeSt.top(); treeSt.pop(); // 取出节点 中
            string path = pathSt.top();pathSt.pop();    // 取出该节点对应的路径
            if (node->left == NULL && node->right == NULL) { // 遇到叶子节点
                result.push_back(path);
            }
            if (node->right) { // 右
                treeSt.push(node->right);
                pathSt.push(path + "->" + to_string(node->right->val));
            }
            if (node->left) { // 左
                treeSt.push(node->left);
                pathSt.push(path + "->" + to_string(node->left->val));
            }
        }
        return result;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/506858.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【CSS】基础选择器

目录 标签选择器 id选择器 类选择器 CSS的编写地点&#xff1a; 标签选择器 说明&#xff1a;标签选择器实际上就是HTML标签元素&#xff08;可以是任何HTML元素&#xff09;&#xff0c;用来改变一个指定标签的样式 示例&#xff1a; <style type"text/css"…

QQ邮箱SMTP发送邮件时要注意哪些安全设置?

QQ邮箱SMTP发送邮件的步骤&#xff1f;如何配置QQ邮箱服务器&#xff1f; 在使用QQ邮箱SMTP发送邮件时&#xff0c;安全设置是至关重要的一环。不当的安全设置不仅可能导致邮件发送失败&#xff0c;还可能使你的账户面临安全风险。下面&#xff0c;AokSend就来详细探讨一下QQ邮…

基于单片机16位智能抢答器设计

**单片机设计介绍&#xff0c;基于单片机16位智能抢答器设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机16位智能抢答器设计是一个结合了单片机技术、显示技术、按键输入技术以及声音提示技术的综合性项目。其设计…

脑机辅助推导算法

目录 一&#xff0c;背景 二&#xff0c;华容道中道 1&#xff0c;问题 2&#xff0c;告诉脑机如何编码一个正方形格子 3&#xff0c;让脑机汇总信息 4&#xff0c;观察图&#xff0c;得到启发式算法 5&#xff0c;根据启发式算法求出具体解 6&#xff0c;可视化 一&am…

苹果App审核大揭秘

苹果上架要求是苹果公司对于提交应用程序到苹果商店上架的要求和规定。这些要求主要是为了保证用户体验、应用程序的质量和安全性。以下是苹果上架要求的详细介绍&#xff1a;1. 应用程序的内容和功能必须符合苹果公司的规 苹果上架要求是苹果公司对于提交应用程序到苹果商店上…

u盘不显示盘符怎么办,u盘不显示盘符

我们经常使用电脑,难免会遇到各种问题,其中U盘不显示盘盘符也是常见的一种。用u盘插入电脑usb接口后,却识别不出u盘,而且更换usb接口以后还是没有u盘盘符,这可怎么用呢?针对此问题,极客狗整理了两个处理方法,接下来带小伙伴一起看看u盘不显示盘符怎么办。遇到同样问题的…

Python数据结构实验 查找实验(一)

一、实验目的 1&#xff0e;熟悉查找的基本概念&#xff0c;包括静态查找表和动态查找表、内查找和外查找之间的差异以及平均查找长度等&#xff1b; 2&#xff0e;掌握线性表上的各种查找算法&#xff0c;包括顺序查找、折半查找和分块查找的基本思路、算法实现和查找效率等…

游戏引擎中的声音系统

一、声音基础 1.1 音量 声音振幅的大小 压强p&#xff1a;由声音引起的与环境大气压的局部偏差 1.2 音调 1.3 音色 1.4 降噪 1.5 人的听觉范围 1.6 电子音乐 将自然界中连续的音乐转换成离散的信号记录到内存中 采样 - 量化 - 编码 香农定理&#xff1a;采样频率是信…

云原生技术精选:探索腾讯云容器与函数计算的最佳实践

文章目录 写在前面《2023腾讯云容器和函数计算技术实践精选集》深度解读案例集特色&#xff1a;腾讯云的创新实践与技术突破精选案例分析——Stable Diffusion云原生部署的最佳实践精选集实用建议分享总结 写在前面 在数字化转型的浪潮下&#xff0c;云计算技术已成为企业运营…

shell脚本发布docker-nginx vue2 项目示例

docker、git、node.js安装略过。 使git pull或者git push不需要输入密码操作方法 nginx安装在docker容器里面&#xff0c;参见&#xff1a;https://blog.csdn.net/HSJ0170/article/details/128631155 姊妹篇&#xff08;宿主机nginx&#xff0c;非docker-nginx&#xff09;&am…

Real-data WRF | setup and run and experiment

前言 Parent Model 用于初始化和边界条件的网格数据 GFS/FNL、NAM、RAP/HRRR、重新分析&#xff08;NARR、CFSR、NNRP、ERA-interim、ERA5 等&#xff09;、其他 WRF 运行 WPS WRF 预处理系统&#xff08;由 geogrid、ungrib 和 metgrid 程序组成&#xff09; WRF 模拟几…

【Linux多线程】生产者消费者模型

【Linux多线程】生产者消费者模型 目录 【Linux多线程】生产者消费者模型生产者消费者模型为何要使用生产者消费者模型生产者消费者的三种关系生产者消费者模型优点基于BlockingQueue的生产者消费者模型C queue模拟阻塞队列的生产消费模型 伪唤醒情况&#xff08;多生产多消费的…

【手册】——mq延迟队列

目录 一、背景介绍二、思路&方案三、过程1.项目为啥用延迟队列&#xff1f;2.项目为啥用三方延迟队列&#xff1f;3.项目中为啥用rabbitmq延迟队列&#xff1f;4.rabbitmq延迟队列的安装5.rabbitmq的延迟队列配置方式5.1.exchange配置5.2.queues配置5.3.exchange和queues的…

文件操作(1)【文件打开和关闭】【文件的顺序读写(各种函数)】【sprintf和sscanf的理解】

一.什么是文件&#xff1f; 在程序设计中我们一般谈的文件有两种&#xff1a;程序文件和数据文件 1.程序文件 程序文件是包含计算机程序代码的文件。它通常包含一系列指令和算法&#xff0c;用于执行特定的任务或实现特定的功能。程序文件可以由不同的编程语言编写&#xff…

【C语言环境】Sublime中运行C语言时MinGW环境的安装

要知道&#xff0c;GCC 官网提供的 GCC 编译器是无法直接安装到 Windows 平台上的&#xff0c;如果我们想在 Windows 平台使用 GCC 编译器&#xff0c;可以安装 GCC 的移植版本。 目前适用于 Windows 平台、受欢迎的 GCC 移植版主要有 2 种&#xff0c;分别为 MinGW 和 Cygwin…

【Python】——变量名的命名规则

&#x1f383;个人专栏&#xff1a; &#x1f42c; 算法设计与分析&#xff1a;算法设计与分析_IT闫的博客-CSDN博客 &#x1f433;Java基础&#xff1a;Java基础_IT闫的博客-CSDN博客 &#x1f40b;c语言&#xff1a;c语言_IT闫的博客-CSDN博客 &#x1f41f;MySQL&#xff1a…

Linux shell编程学习笔记42:md5sum

0 前言 前几天在国产电脑上遇到一个问题&#xff0c;先后接到两个文件&#xff0c;如何判断这两个文件内容是否相同&#xff1f; 如果是在Windows系统&#xff0c;可以用fc命令&#xff0c;或者用我自己写的FileInfo&#xff0c;提取两个文件有MD5、SHA1、CRC32值进行比较来判…

GANs和Diffusion模型(3)

接GANs和Diffusion模型&#xff08;2&#xff09; 扩散(Diffusion)模型 生成学习三重困难(Trilemma) 指生成学习(genrative learning)的模型都需要满足三个需求&#xff1a; 高质量的采样(High Quality Samples)&#xff1a;模型应该能生成非常高质量的采样快速采样(Fast S…

使用 Python 模拟布朗运动(和股票价格)

一、说明 本文先介绍布朗运动的概念&#xff0c;紧接着应用布朗方程到股票的随机斩落模型。进而用python实现&#xff0c;并给出各种各样的条件模型。从中烘托出股票模型的规律所在。 二、什么是布朗运动&#xff1f; 布朗运动以罗伯特布朗的名字命名&#xff0c;他是第一个在通…

持续交付与持续部署相关概念(CD)

目录 一、概述 二、持续交付基本概念 2.1 持续交付的含义 2.1.1 项目管理的视角 2.1.2 产品研发的视角 2.1.3 总结 2.2 持续交付涉及的运作环境 2.2.1 开发环境 2.2.2 测试环境 2.2.3 UAT环境 2.2.4 准生产环境 2.2.5 生产环境 2.3 总结 三、持续部署基本概念 3.…