求解:二叉树中的回溯问题!!!

求二叉树的所有路径和题目如下:
给定一个二叉树,返回所有从根节点到叶子节点的路径。
代码:
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;

    }
};


现在想把左右子树的那两个if语句这样写
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();
}
这是我看一个大佬的代码,我不理解回溯那里为什么要pop两次??我觉得一次就够了啊,因为递归返回的时候path的值并没有变啊,只要把加的那个‘-》’删掉就可以了啊。想不明白,求解答

#C/C++#
全部评论
你这是没理解回溯的基本思想啊,path加了“->”两个字符,回溯后不就得弹出两个字符,仅此而已
点赞 回复 分享
发布于 2022-03-04 17:20
求大佬解答!!
点赞 回复 分享
发布于 2022-03-04 16:29

相关推荐

评论
1
收藏
分享

创作者周榜

更多
正在热议
更多
# 长得好看会提高面试通过率吗? #
4471次浏览 48人参与
# 离家近房租贵VS离家远但房租低,怎么选 #
16917次浏览 137人参与
# 巨人网络春招 #
11550次浏览 229人参与
# 沪漂/北漂你觉得哪个更苦? #
1616次浏览 41人参与
# 你的实习产出是真实的还是包装的? #
3230次浏览 54人参与
# 春招至今,你的战绩如何? #
16140次浏览 146人参与
# 米连集团26产品管培生项目 #
7387次浏览 226人参与
# HR最不可信的一句话是__ #
1107次浏览 32人参与
# AI面会问哪些问题? #
971次浏览 24人参与
# 你做过最难的笔试是哪家公司 #
1306次浏览 23人参与
# AI时代,哪个岗位还有“活路” #
2930次浏览 53人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
152954次浏览 889人参与
# 简历第一个项目做什么 #
32195次浏览 363人参与
# 军工所铁饭碗 vs 互联网高薪资,你会选谁 #
8032次浏览 43人参与
# XX请雇我工作 #
51164次浏览 171人参与
# 简历中的项目经历要怎么写? #
311149次浏览 4272人参与
# 投格力的你,拿到offer了吗? #
178382次浏览 891人参与
# 你最满意的offer薪资是哪家公司? #
77008次浏览 375人参与
# AI时代,哪些岗位最容易被淘汰 #
64856次浏览 893人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
187643次浏览 1123人参与
# 你怎么看待AI面试 #
180882次浏览 1318人参与
# 正在春招的你,也参与了去年秋招吗? #
364407次浏览 2642人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务