题目
257 二叉树的所有路径
给定一个二叉树,返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例
输入:root = [1,2,3,null,5]
输出:[“1->2->5”,”1->3”]
思路
本题用到了回溯的思想。
本题要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径。而且我们要把路径记录下来,当一个路径在进入另一个路径时需要回溯来回退。
本题需要如下的递归函数
- 递归定义:
void getTreePaths(TreeNode* cur, vector<int>& path, vector<string>& result)
- 输入node, 返回记录的路径和结果vector
- 递归终止条件
- node为空,直接返回
- node左右子节点为空, 根据当前节点和path生成string,添加到result中,返回
- 不符合递归终止条件,则添加当前节点值到path,继续递归
再看回溯,回溯和递归是一一对应的,有一个递归,就要有一个回溯,所以在每次递归返回后,都要进行回溯。
本题中递归只会把当前节点添加到path中,回溯意味着把当前节点从path中删除,不然下次进入递归时path中会存在错误的节点值。
class Solution
{
public:
vector<string> binaryTreePaths(TreeNode *root)
{
if (root == nullptr)
return {};
vector<int> path; //记录一条路径, 用于回溯
vector<string> vec;
getTreePaths(root, path, vec);
return vec;
}
private:
void getTreePaths(TreeNode *cur, vector<int> &path, vector<string> &result)
{
if (cur == nullptr) //终止条件1
return;
//添加当前节点到path
path.push_back(cur->val);
//判断是否符合递归终止条件2
if (cur->left == nullptr && cur->right == nullptr)
{
string tmp;
for (auto p : path)
{
tmp += std::to_string(p) + "->";
}
tmp.resize(tmp.size() - 2); //去除末尾->
result.push_back(tmp);
return;
}
if (cur->left != nullptr)
{
//递归左子节点
getTreePaths(cur->left, path, result);
//回溯
path.pop_back(); //这里把左子节点移除
}
if (cur->right != nullptr)
{
//递归右子节点
getTreePaths(cur->right, path, result);
//回溯
path.pop_back(); //这里把右子节点移除
}
return;
}
};