257. Binary Tree Paths

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

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

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

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Solution

Approach 1: Recursion.

Approach 2: Iteration.

Code (Python)

Approach 1:

Approach 2:

Code (C++)

Approach 1:

/**
 * 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> paths;
        binaryTreePaths(root, paths, "");
        return paths;
    }
    void binaryTreePaths(TreeNode* root, vector<string>& paths, string path) {
        if (root)
        {
            path += to_string(root->val);
            if (!root->left && !root->right)
                paths.push_back(path);
            else
            {
                path += "->";
                binaryTreePaths(root->left, paths, path);
                binaryTreePaths(root->right, paths, path);
            }
        }
    }
};

Approach 2:

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        stack<TreeNode*> nodeStack;
        stack<string> pathStack;
        nodeStack.push(root);
        pathStack.push("");
        while (!nodeStack.empty())
        {
            TreeNode *node = nodeStack.top();
            nodeStack.pop();
            string path = pathStack.top();
            pathStack.pop();
            if (node)
            {
                path += to_string(node->val);
                if (!node->left && !node->right)
                    paths.push_back(path);
                else
                {
                    path += "->";
                    nodeStack.push(node->left);
                    pathStack.push(path);
                    nodeStack.push(node->right);
                    pathStack.push(path);
                }
            }
        }
        return paths;
    }
};