257 - Binary Tree Paths

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"]

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Hide Tags
Tree
Hide Similar Problems
(M) Path Sum II

DFS，沿途修改字符串，到叶子push结果，没啥好说的。

/**
* 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> rst;
        string buf;
        if(root)
            dfs(root, buf, rst);
        return rst;
    }
   
    void dfs(TreeNode* node, string& buf, vector<string>& rst)
    {
        int len = buf.length();
        buf += to_string(node->val);
        len = buf.length() - len;

        if(NULL==node->left && NULL==node->right)
            rst.push_back(buf);
        else
        {
            if(NULL != node->left)
            {
                buf += "->";
                dfs(node->left, buf, rst);
                buf.pop_back(), buf.pop_back();
            }
            if(NULL != node->right)
            {
                buf += "->";
                dfs(node->right, buf, rst);
                buf.pop_back(), buf.pop_back();
            }
        }
        while(len--)
            buf.pop_back();
        return;
    }
};4 ms.