Non-recursive C++ solution (4ms) with explanation


  • 0
    E

    This is a DFS problem. The idea is to maintain a path to current node. This path can only store the node values on the path since we only need to output the values. You can do it either recursively or iteratively. For recursion, you can pass the current path by reference or use a member variable. For iteration, it is more obvious. Here I use iterations and a vector to store the path.

    We need to maintain a correct length of path vector according to the current level of the traversal. For recursion, you can passing the level by a parameter. For iteration, you can passing the level along with the node on the stack. I use a pair to pairing node and level number to store the correct level number.

    Any words?

    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> result;
            if (!root) return result;
            vector<int> path;
            stack< pair<TreeNode*, int> > s;
            s.push(make_pair(root, 0));
            while (!s.empty()) {
                int level = s.top().second;
                path.resize(level);
                TreeNode * node = s.top().first;
                s.pop();
                path.push_back(node->val);
                if (!node->left && !node->right) {
                    string pathstr;
                    for (int i = 0; i < path.size(); ++i) {
                        pathstr += to_string(path[i]) + ((i != path.size() - 1) ? "->" : "");
                    }
                    result.push_back(pathstr);
                } else {
                    if (node->right) s.push(make_pair(node->right, level + 1));
                    if (node->left) s.push(make_pair(node->left, level + 1));
                }
            }
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.