[LeetCode] Binary Tree Paths 二叉树路径-白红宇

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1 /   \2     3 \  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

这道题给我们一个二叉树，让我们返回所有根到叶节点的路径，跟之前那道很类似，比那道稍微简单一些，不需要计算路径和，只需要无脑返回所有的路径即可，那么思路还是用DFS来解，代码而很简洁，参见如下：

解法一：

class Solution {public:    vector
      
        binaryTreePaths(TreeNode* root) {        vector
       
         res;        if (root) dfs(root, "", res);        return res;    }    void dfs(TreeNode *root, string out, vector
        
          &res) {        out += to_string(root->val);        if (!root->left && !root->right) res.push_back(out);        else {            if (root->left) dfs(root->left, out + "->", res);            if (root->right) dfs(root->right, out + "->", res);        }    }};

下面再来看一种递归的方法，这个方法直接在一个函数中完成递归调用，不需要另写一个dfs函数，核心思想和上面没有区别，参见代码如下：

解法二：

class Solution {public:    vector
      
        binaryTreePaths(TreeNode* root) {        if (!root) return {};        if (!root->left && !root->right) return {to_string(root->val)};        vector
       
         left = binaryTreePaths(root->left);        vector
        
          right = binaryTreePaths(root->right);        left.insert(left.end(), right.begin(), right.end());        for (auto &a : left) {            a = to_string(root->val) + "->" + a;        }        return left;    }};

本文转自博客园Grandyang的博客，原文链接：，如需转载请自行联系原博主。