题目描述

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

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

样例

输入：

   1
 /   \
2     3
 \
  5

输出：["1->2->5", "1->3"]

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

算法

(递归回溯) $O(n^2)$

1. 从根结点开始递归遍历，每个结点仅遍历一次，遍历时需要记录当前路径。
2. 若发现当前结点没有左右儿子，则当前结点为叶子结点，将当前路径加入答案。

时间复杂度

• 每个结点仅遍历一次，遍历时维护路径所需要的平均时间也和遍历时间成正比。
• 最坏情况下，每条路径需要 $O(n)$ 的时间存放，共有 $O(n)$ 个叶子节点，故总时间复杂度为 $O(n^2)$，可以参考评论里的图。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    string arrayToString(const vector<int> &path) {
        string res(to_string(path[0]));
        for (int i = 1; i < path.size(); i++) {
            res += "->";
            res += to_string(path[i]);
        }

        return res;
    }

    void solve(TreeNode *cur, vector<int> &path, vector<string>& ans) {
        path.push_back(cur->val);

        if (cur->left == NULL && cur->right == NULL) {
            ans.push_back(arrayToString(path));
        } else {
            if (cur->left != NULL) solve(cur->left, path, ans);
            if (cur->right != NULL) solve(cur->right, path, ans);
        }

        path.pop_back();
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        if (root == NULL)
            return ans;

        vector<int> path;
        solve(root, path, ans);

        return ans;
    }
};