LeetCode 257. 二叉树的所有路径 思考分析

目录

题目思路一：深度递归思路二：广度迭代关于回溯

题目

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

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

输出: [“1->2->5”, “1->3”]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

思路一：深度递归

void traversal(TreeNode* cur , vector<string>& paths,string path) { if(cur == NULL) return; path+=to_string(cur->val); //如果是叶子结点，返回将path送入paths，然后return回去 if(!cur->left && !cur->right) { paths.push_back(path); } //如果不是叶子结点，将该结点加入路径,然后继续遍历左右子结点 else { path+= "->"; traversal(cur->left,paths,path); traversal(cur->right,paths,path); } return; }

之前我一直在思考一个问题，就是如果我已经完成了一条路径，那么必定要向上回溯到上面的结点，那么此时的path又该是怎样的呢？ 在我一开始的认为中，path会直接在原有的已完成的一条路径上再次添加->，但仔细一想，并不是这样。 以下面的树为例：

1 / \ 2 3 \ 5

遍历的结点输入前的path输入后的pathpaths11->21->1->2->2的左孩子NULL1->2->1->2->51->2->1->2->51->2->52(return的时候，返回到原来的函数，参数仍然是原来函数的参数)1->1->21->2->51(return的时候，返回到原来的函数，参数仍然是原来函数的参数)1->1->2->531->1->31->2->5,1->31(return的时候，返回到原来的函数，参数仍然是原来函数的参数)1->1->2->5,1->3

最后return根结点。

返回到上一级的时候path会被重置为上一级函数的path，而vector中的值不会被修改，因为我们使用的是&，vector中的值已经被修改了。

AC代码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void traversal(TreeNode* cur , vector<string>& paths,string path) { if(cur == NULL) return; path+=to_string(cur->val); //如果是叶子结点，返回将path送入paths，然后就该 if(!cur->left && !cur->right) { paths.push_back(path); } //如果不是叶子结点，将该结点加入路径,然后继续遍历左右子结点 else { path+= "->"; traversal(cur->left,paths,path); traversal(cur->right,paths,path); } return; } vector<string> binaryTreePaths(TreeNode* root) { vector<string> paths; string path =""; traversal(root,paths,path); return paths; } };

感觉对于回溯的思想还是很陌生，等二叉树的题目练完了就去找几个回溯的练练手。 递归就是函数的嵌套调用，函数调用的时候会将参数存入栈中，所以返回到上一级函数时，参数会自动拨正。

思路二：广度迭代

维护一个队列，存储结点以及根到该结点的路径。 一开始这个队列里面只有根结点。 每一步迭代中，我们取出队列中的首结点，如果它是叶子结点，则将它对应的路径加入到答案中。 如果它不是叶子结点，则将它的所有孩子结点加入到队列的末尾。当队列为空时广度优先搜索结束。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<string> binaryTreePaths(TreeNode* root) { vector<string> paths; if(root == NULL) { return paths; } queue<TreeNode*> node_queue; queue<string> path_queue; node_queue.push(root); path_queue.push(to_string(root->val)); while(!node_queue.empty()) { TreeNode* node = node_queue.front(); string path = path_queue.front(); node_queue.pop(); path_queue.pop(); if(node->left == NULL && node->right == NULL) { paths.push_back(path); } else { if(node->left !=NULL) { node_queue.push(node->left); path_queue.push(path+"->"+to_string(node->left->val)); } if(node->right !=NULL) { node_queue.push(node->right); path_queue.push(path+"->"+to_string(node->right->val)); } } } return paths; } };

关于回溯

class Solution { public: void traversal(TreeNode* cur,vector<int>& path,vector<string>& paths) { path.push_back(cur->val); //如果是叶子结点 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]); paths.push_back(spath); } //不是叶子结点 if(cur->left) { traversal(cur->left,path,paths); path.pop_back();//回溯 } if(cur->right) { traversal(cur->right,path,paths); path.pop_back();//回溯 } } vector<string> binaryTreePaths(TreeNode* root) { vector<string> paths; vector<int> path; if(root == NULL) return paths; traversal(root,path,paths); return paths; } };

注意这里对子路径path使用了&，所以一旦改变之后，就无法返回到上一个函数的参数了，所以需要进行pop_back进行回溯。