给你一个二叉树的根节点 root,按任意顺序返回所有从根节点到叶子节点的路径。
示例如下:
本题需要使用前序遍历加回溯,我们要把路径记下来然后回溯退出一个路径再进入另一个路径。
1.迭代法
前序遍历迭代来模仿遍历路径的过程,需要一个栈存放节点以及一个栈存放对应遍历的路径,实现代码如下:
//Solution1---迭代法
vector<string> binaryTreePaths(TreeNode* root) {
stack<TreeNode*> treeSt; //保存树的遍历节点
stack<string> pathSt; //保存遍历路径的结点
vector<string> result; //保存结果
if (root == NULL) return result;
treeSt.push(root);
pathSt.push(to_string(root->val));
while(!treeSt.empty()) {
TreeNode* node = treeSt.top(); treeSt.pop();
string path = pathSt.top(); pathSt.pop();
if(node->left == NULL && node->right == NULL) {
result.push_back(path);
}
if(node->right) {
treeSt.push(node->right);
pathSt.push(path+"->"+to_string(node->right->val));
}
if(node->left) {
treeSt.push(node->left);
pathSt.push(path+"->"+to_string(node->left->val));
}
}
return result;
}
2.递归法
递归三部曲:
(1)确定参数和返回值:参数为传入的结点,记录路径的path以及存放结果,无返回值;
(2)确定终止条件:当遇到根节点时处理结果;
(3)确定单层递归的逻辑:处理中间节点放入path中,然后进行递归和回溯。
实现代码如下:
//Solution2--递归法
void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {
path.pash_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]);
result.push_back(spath);
return;
}
if (cur->left) {
traversal(cur->left, path, result);
path.pop_back(); //回溯
}
if(cur->right) {
traversal(cur->right, path, result);
path.pop_back(); //回溯
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
if (root == NULL) return result;
traversal(root, path, result);
return result;
}