求解:二叉树中的回溯问题!!!
求二叉树的所有路径和题目如下:
给定一个二叉树,返回所有从根节点到叶子节点的路径。
代码:
现在想把左右子树的那两个if语句这样写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 (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的值并没有变啊,只要把加的那个‘-》’删掉就可以了啊。想不明白,求解答 
查看14道真题和解析
传音控股公司福利 360人发布