257-二叉树的所有路径

LeetCode 257. Binary Tree Paths

LeetCode-257

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5]
   1
 /   \
2     3
 \
  5
Output: ["1->2->5","1->3"]

method: 回溯

用vector存储路径和回溯比较方便，后面再转成string

• 函数参数和返回值：前序遍历的当前节点
• 递归结束条件：节点为叶子节点
• 左右子树非空才进行递归，回溯时要把左右子树的节点pop出来

vector<int> path;
vector<string> ret;
void traversal(TreeNode* root) {
    if (!root) return;  // 这里处理空节点
    path.push_back(root->val);  // 每个节点push一次
    if (!root->left && !root->right) {
        string s;
        for (int i = 0; i < path.size(); ++i) {
            if (i) s += "->";
            s += to_string(path[i]);
        }
        ret.push_back(s);   // 这里不能加return，不然叶子节点没pop出去
    }
    traversal(root->left);  // 先递归
    traversal(root->right);
    path.pop_back();    // pop一次
}
vector<string> binaryTreePaths(TreeNode* root) {
    traversal(root);
    return ret;
}

直接把path作为递归参数也可以

vector<string> res;
void dfs(TreeNode *root, string path) {
    if (!root) return;
    path += to_string(root->val);
    if (!root->left && !root->right) {
        res.push_back(path);
    }
    path += "->";
    dfs(root->left, path);
    dfs(root->right, path);
}
vector<string> binaryTreePaths(TreeNode* root) {
    dfs(root, "");
    return res;
}