C++ recursive and iterative solutions with detailed comments


  • 6
    Z

    The recursive solution is trivial.

    class Solution 
    {
    public:
        vector<string> binaryTreePaths(TreeNode* root) 
        {
            vector<string> paths;
            // If root is NULL, return an empty path vector.
            if (root == nullptr)
            {
                return paths;
            }
            
            // Get the path vector starting from the left child.
            vector<string> leftPaths = binaryTreePaths(root->left);
            // Concatenate root with the left paths to generate 
            // the paths starting from root.
            for (auto& lp : leftPaths)
            {
                paths.push_back(to_string(root->val) + "->" + lp);
            }
            
            // Get the path vector starting from the right child.
            vector<string> rightPaths = binaryTreePaths(root->right);
            // Concatenate root with the right paths to generate 
            // the paths starting from root.
            for (auto& rp : rightPaths)
            {
                paths.push_back(to_string(root->val) + "->" + rp);
            }
            
            // In case that both leftPaths and rightPaths are empty, 
            // i.e., root is a leaf, root itself is a path.
            if (paths.empty())
            {
                paths.push_back(to_string(root->val));
            }
            
            return paths;
        }
    };
    

    The iterative solution essentially uses the depth-first search to find all the paths from root to leaves. Compared with the breadth-first search approach, this approach doesn't need to have a vector of vectors to keep the paths from root to the nodes at the current level. Besides the result vector of strings, this approach just needs one vector which keeps one path from root to the current node and one unordered set which keeps all the nodes that have been visited during the depth-first search. Thus, with respect the space complexity, the depth-first search is more efficient than the breadth-first search.

    class Solution 
    {
        // Generate the path string from the TreeNode val vector.
        string GetPathStringFromNums(vector<int> &pathVal)
        {
            int n = pathVal.size();
            string res;
            // For the nodes except the last node, we need to 
            // append "->" to the node values.
            for (int i = 0; i < n - 1; i++)
            {
                res += (to_string(pathVal[i]) + "->");
            }
            
            if (n > 0)
            {
                res += to_string(pathVal[n - 1]);
            }
            
            return res;
        }
        
    public:
        vector<string> binaryTreePaths(TreeNode* root) 
        {
            vector<string> paths;
            // If root is NULL, return an empty path vector immediately.
            if (root == nullptr)
            {
                return paths;
            }
            
            // pathVal is a vector of TreeNode values along a path 
            // starting from root.
            vector<int> pathVal({root->val});
            
            // st is the stack used for the depth-first search.
            stack<TreeNode*> st;
            st.push(root);
            
            // visitedNodes keeps all the nodes which have been visited 
            // during the depth-first search. In other words, it keeps 
            // all the nodes which have ever been pushed into the stack.
            unordered_set<TreeNode*> visitedNodes({root});
            
            // Do the depth-first search until the stack is empty.
            while (!st.empty())
            {
                TreeNode *curr = st.top();
    
                if ((curr->left == nullptr) && (curr->right == nullptr))
                {
                    // curr is a leaf, so the current path is a path from 
                    // root to a leaf and add it to paths.
                    paths.push_back(GetPathStringFromNums(pathVal));
                    
                    // Remove the leaf node from pathVal which will end at 
                    // the parent node of curr.
                    pathVal.pop_back();
                    
                    st.pop();
                }
                else 
                {
                    // curr is not leaf, so we need to go down at least one 
                    // level.
                    
                    // First we try pushing the left child if it hasn't 
                    // been visited.
                    if (curr->left != nullptr)
                    {
                        auto itLeft = visitedNodes.find(curr->left);
                        if (itLeft == visitedNodes.end())
                        {
                            st.push(curr->left);
                            pathVal.push_back(curr->left->val);
                            
                            visitedNodes.insert(curr->left);
                            continue;
                        }
                    }
                    
                    // We reach here because either the left child doesn't 
                    // exist or the left child has been visited. Then we try 
                    // pushing the right child if it hasn't been visited.
                    if (curr->right != nullptr)
                    {
                        auto itRight = visitedNodes.find(curr->right);
                        if (itRight == visitedNodes.end())
                        {
                            st.push(curr->right);
                            pathVal.push_back(curr->right->val);
                            
                            visitedNodes.insert(curr->right);
                            continue;
                        }
                    }
                    
                    // The nodes in the subtree below curr have all been 
                    // visited, so remove curr from pathVal which will end 
                    // at the parent node of curr.
                    pathVal.pop_back();
                    st.pop();
                }
            }
            
            return paths;
        }
    };

  • 0
    M

    Nice solution and coding style!


  • 0
    Z

    Thank you, mathsam.


Log in to reply
 

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