一.解法

https://leetcode-cn.com/problems/binary-tree-paths/
要點(diǎn)：遞歸，DFS
Python，C++，Java都用了遞歸的方法。
用了dfs的思想，用一個(gè)輔助的path表示當(dāng)前路徑，遞歸時(shí)這個(gè)路徑會繼承給孩子，當(dāng)?shù)竭_(dá)葉子節(jié)點(diǎn)時(shí)返回這個(gè)路徑給res（保存答案的vector string）。

二.Python實(shí)現(xiàn)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        def construct_paths(root, path):
            if root:
                path += str(root.val)
                if not root.left and not root.right:  # 當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)
                    paths.append(path)  # 把路徑加入到答案中
                else:
                    path += '->'  # 當(dāng)前節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，繼續(xù)遞歸遍歷
                    construct_paths(root.left, path)
                    construct_paths(root.right, path)

        paths = []
        construct_paths(root, '')
        return paths

三.C++實(shí)現(xiàn)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        if (root == nullptr) return res;

        binaryTreePaths(root, res, "");
        return res;
    }

    void binaryTreePaths(TreeNode * root, vector<string> & res, string path) {
        path += to_string(root->val);

        if (root->left == nullptr && root->right == nullptr) {
            res.push_back(path);
            return;
        }

        if (root->left) binaryTreePaths(root->left, res, path + "->");
        if (root->right) binaryTreePaths(root->right, res, path + "->");
    }
};

四.java實(shí)現(xiàn)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void construct_paths(TreeNode root, String path, LinkedList<String> paths) {
        if (root != null) {
            path += Integer.toString(root.val);
            if ((root.left == null) && (root.right == null))  // 當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)
                paths.add(path);  // 把路徑加入到答案中
            else {
                path += "->";  // 當(dāng)前節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，繼續(xù)遞歸遍歷
                construct_paths(root.left, path, paths);
                construct_paths(root.right, path, paths);
            }
        }
    }

    public List<String> binaryTreePaths(TreeNode root) {
        LinkedList<String> paths = new LinkedList();
        construct_paths(root, "", paths);
        return paths;
    }
}