【二叉树】【回溯】二叉树的所有路径详解【力扣.257】超详细的宝藏教程_回溯法遍历二叉树

【二叉树】【回溯】二叉树的所有路径详解【力扣.257】超详细的宝藏教程

先赞后看好习惯 打字不容易，这都是很用心做的，希望得到支持你 大家的点赞和支持对于我来说是一种非常重要的动力 看完之后别忘记关注我哦！️️️

强烈建议本篇收藏后食用~

力扣OJ.257：257. 二叉树的所有路径

说在前面：
由于二叉树的结构特点，回溯算法，是我们在学习二叉树的时候，必不可少的工具。因此今天，博主带着大家，用回溯算法的三部曲，拿下这道经典的题目。

题目中树的结构：

//树的结构
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
1
2
3
4
5
6
7
8

这是博主另外一篇关于回溯算法的题目，里面讲解了回溯算法的解题模板，这里提供传送门供大家食用(都进去支持一下吧哈哈哈)：【算法】【回溯】N皇后问题【力扣-51】超详细的注释和解释手撕N皇后

题目描述

算法分析

首先，很明显，这道题是肯定要用回溯的，如图： 图片来自：代码随想录
在这里，博主带大家回顾一下回溯算法的三部曲：

1. 确定递归函数参数和返回值
2. 确定递归终止条件
3. 确定单层递归逻辑

一. 确定递归函数参数和返回值
传入二叉树根节点是必须要的，当然我们还需要一个数组path，和一个结果数组ret。
path用在每条路径上添加节点，当每遇到一个节点push_back()一下，到叶子节点了，就push_back()进ret里面。

void traveral(TreeNode* cur, vector<int>& path, vector<string>& ret)
1

二. 确定递归终止条件
很明显，当遇到叶子节点的时候，递归终止。

 if (cur->left == NULL && cur->right == NULL)
1

当然，终止之后我们是要做事情的。

• 将path里面的东西转化成字符串，最后push_back()进ret里面。

具体代码博主将在完整代码里面做讲解。

三. 确定单层递归逻辑
当然，单层搜索就是递归了

• 递归回溯永不分离
• 一次递归伴随着一次回溯

所以我们每次递归完一定要记得撤销，回溯。

完整代码实现

class Solution {
private:
    void traveral(TreeNode* cur, vector<int>& path, vector<string>& ret) {
        //因为是前序遍历，所以第一步是先处理根，后面才有递归和回溯
        path.push_back(cur->val);
        //把根push_back()进去之后，才认为到了叶子节点，才开始判断
        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]);//把最后那个搞进去
            ret.push_back(sPath);
        }
        //记住，有递归就有回溯
        //一定是要将刚进去那个pop_back()出来之后，才能回溯
        //回溯递归永不分离
        //所以pop_back()操作一定是在if的{}里面的，一个递归就有一个回溯
        if (cur->left) {
            traveral(cur->left, path, ret);
            path.pop_back();
        }
        if (cur->right) {
            traveral(cur->right, path, ret);
            path.pop_back();
        }
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string>ret;
        vector<int>path;
        if (root == NULL)return ret;
        traveral(root, path, ret);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

尾声

看到这里，相信伙伴们对这道经典回溯算法解决二叉树的问题已经有了一定理解了。
最后，如果你感觉在这篇文章里学到东西的话，千千万万不要忘了点赞收藏关注后再离开哦！