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

二叉树的所有路径

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

#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x)
    {
        val=x;
        left=NULL;
        right=NULL;
    }
};
void traversal(TreeNode* node,vector<int>& path,vector<string>& result)
{
    path.push_back(node->val);
    if(node->left==NULL&&node->right==NULL)
    {
        string paths;
        for(int i=0;i<path.size()-1;i++)
        {
            paths+=to_string(path[i]);
            paths+="->";
         } 
        paths+=to_string(path[path.size()-1]);
        result.push_back(paths);
        return ;
    }
    if(node->left)
    {
        traversal(node->left,path,result);
        path.pop_back();
    }
    if(node->right)
    {
        traversal(node->right,path,result);
        path.pop_back();
    }
    return;
}
vector<string> biary(TreeNode* root)
{
    vector<int> path;
    vector<string> result;
    if(root==NULL)
    return result;
    traversal(root,path,result);
    return result;
}
int main()
{
    TreeNode* root=new TreeNode(1);
    root->left=new TreeNode(2);
    root->right=new TreeNode(3);
    root->left->right=new TreeNode(5);
    vector<string> result=biary(root);
    for(string c:result)
    {
        cout<<c<<endl;
     } 
    return 0;
}
思路:在这里我们需要从上向下确定路径即从父结点到子结点,所以我们使用前序遍历,这道题目中涉及到回溯,因为我们要把路径记录下来,需要回溯来回退一个路径再进入另一个路径。

在这里我们用path来记录路径,用result返回结果,确定的终止条件即当遍历到叶子结点时,我们将此时path里面收集到的val转换成路径形式存到result中。
遍历过程中如果存在左子树,就递归遍历,同时要记得回溯(path.pop_back()),因为此时已经将记录存在result中了,我们要开始收集下一条路径·,因此要回溯,同样存在右子树,也要递归遍历,也得回溯,所有路径都被保存到result中。


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

相关文章:

  • Python 与 JavaScript 交互及 Web 逆向分析全解析
  • 手机遥控开关技术解析与应用指南
  • C 语言分支与循环:构建程序逻辑的基石
  • 字符串哈希
  • 【硬件测试】基于FPGA的16PSK+帧同步系统开发与硬件片内测试,包含高斯信道,误码统计,可设置SNR
  • 数学建模之数学模型-3:动态规划
  • C# 集合
  • 卷积神经网络(CNN)之 EfficientNet
  • 【RTSP】客户端(三) 音频相关
  • 计算机视觉算法实战——花卉识别(主页有源码)
  • Spring框架详解(IOC容器-上)
  • JVM 如何保证 Java 程序的安全性?
  • TypeScript 高级类型 vs JavaScript:用“杂交水稻”理解类型编程
  • 【redis】set 类型:基本命令
  • 遥感数据获取、处理、分析到模型搭建全流程学习!DeepSeek、Python、OpenCV驱动空天地遥感数据分析
  • WPF程序使用AutoUpdate实现自动更新
  • Secs/Gem第一讲(基于secs4net项目的ChatGpt介绍)
  • 完善机器人:让 DeepSeek 使用Vue Element UI快速搭建 AI 交互页面
  • 【Linux系统编程】管道
  • 什么是mysql索引回表?