lc.257 到叶子的所有路径

方法1：## 深度优先搜索DFS（递归版）

class Solution {
public:

vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> res; // 存储结果路径
    dfs(root, "", res); // 调用辅助函数
    return res;
}
  

void dfs(TreeNode* root, string path, vector<string>& res) {

    // 如果节点为空，直接返回
    if (root == nullptr)
        return;
  
    // 如果是叶子节点，将路径加入结果中
    if (root->left == nullptr && root->right == nullptr) {
        res.push_back(path + to_string(root->val));//dfs函数没有返回值，唯一的操作是通过这一句,只有在遇到叶子结点的时候才会把string添加到res里
        return;
    }

    // 如果不是叶子节点，继续递归处理左右子节点
    dfs(root->left, path + to_string(root->val) + "->", res);//往path添加root的值
    dfs(root->right, path + to_string(root->val) + "->", res);

}
};

==string是非引用传参==

void函数可直接return而不指定返回值(主要用于提前退出函数)

![[Pasted image 20241125120242.png

200]]

#写树的递归
先把目光局限在一个三结点的二叉树中：
![[Pasted image 20241125120412.png|100]]

1. 如果根节点root同时具有左右孩子，要做什么操作？
2. 如果root只有一个左/右孩子，要做什么操作？
3. 如果root没有子结点（叶子节点），要做什么操作？
4. 如果root为null，要做什么操作？

拿这道题为例子：

1. 如果根节点root同时具有左右孩子，要做什么操作？
   要把root->val加入字符串path中，然后分别递归处理左右孩子
   dfs(root->left, path + to_string(root->val) + "->", res);
dfs(root->right, path + to_string(root->val) + "->", res);
2. 如果root只有一个左/右孩子，要做什么操作？
   和 同时具有左右孩子 一样（不做区分）
3. 如果root没有子结点（叶子节点），要做什么操作？
   res.push_back(path + to_string(root->val));遇到叶子节点，这一条path就可以添加到res中了
4. 如果root为null，要做什么操作？
   直接return