题目描述
https://leetcode-cn.com/problems/binary-tree-paths/
思路
回溯第一题~~~~
果然脑子转不过弯,但是呢呢给讲了下我立马就明白了,在这记录下。
回溯和递归的区别,就是回溯需要修改状态,因此需要恢复现场,而递归不一定。具体说明:
题目中给的二叉树的例子,从1出发找路径,可以去左孩子2,也可以去右孩子3。
往左孩子探的话,路径字符串 1->2。往右孩子探的话,路径字符串1->3.
你探完左孩子,再回到1(回溯),去探右孩子之前,路径字符串必须由1->2再恢复成1(恢复现场),再去探右孩子.
不然探右孩子的时候,路径字符串就变成了1->2->3.
明白了就好写了。
但是这个题,路径字符串可以直接用string,而不是string &,这样就省得回溯回去的时候恢复这个路径字符串了。
然后结合代码,好好体会下就算入门了。
以后要做的八皇后问题也是这样,往下走每一步都有8个选择,每个选择探完回到原点都要恢复现场,再去探下一个选择。
代码
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> paths;
if (root) findPath(root, paths, "");
return paths;
}
void findPath(TreeNode* root, vector<string>& paths, string s) {
if (!root->left && !root->right) paths.push_back(s+to_string(root->val));
if (root->left) findPath(root->left, paths, s + to_string(root->val) + "->");
if (root->right) findPath(root->right, paths, s + to_string(root->val) + "->");
}
};
follow up
113. 路径总和 II
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<int> one;
if (!root) return res;
dfs(root, sum, one, res);
return res;
}
void dfs(TreeNode* root, int sum, vector<int> one, vector<vector<int>>& res) {
one.push_back(root->val);
if (!root->left && !root->right) {
if (sum == root->val) {
res.push_back(one);
}
}
if (root->left) dfs(root->left, sum - root->val, one, res);
if (root->right) dfs(root->right, sum - root->val, one, res);
}
};
网友评论