C++/C# recursive / iterative with backtracking solution


  • 0
    O

    C++ revursive

     vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
    
        if(root != NULL)
        {
            // use dictionary to keep parent info to reconstruct the path
            unordered_map<TreeNode*, TreeNode*> parent;
            PathSumHelper(root, sum, res, parent);
        }
        
        return res;
    }
    
    void PathSumHelper(TreeNode* root, int sum, vector<vector<int>>& res, 
    unordered_map<TreeNode*, TreeNode*>& parent)
    {
        if(!root->left && !root->right && root->val == sum)
        {
            vector<int> path;
            // Find path using parents dictionary to reconstruct the path
            while(root)
            {
                // insert at the begining to keep order
                path.insert(path.begin(), root->val);
                unordered_map<TreeNode*, TreeNode*>::const_iterator par =
                parent.find(root);
                if(par != parent.end())
                {
                    root = par->second;
                }
                else
                {
                    root = NULL;
                }
            }
            
            // Add to the list of results
            res.push_back(path);
        }
        else
        {
            if(root->left)
            {
                parent.insert(pair<TreeNode*,TreeNode*>(root->left, root));
                PathSumHelper(root->left, sum - root->val, res, parent); 
            }
            
            if(root->right)
            {
                parent.insert(pair<TreeNode*,TreeNode*>(root->right, root));
                PathSumHelper(root->right, sum - root->val, res, parent); 
            }
        }
    }
    

    C# iterative

    public IList<IList<int>> PathSum(TreeNode root, int sum) {
        IList<IList<int>> res = new List<IList<int>>();
    
        if(root != null)
        {
            IDictionary<TreeNode, TreeNode> parent =
            new Dictionary<TreeNode, TreeNode>();
            Stack<TreeNode> nodeStack = new Stack<TreeNode>();
            Stack<int> sumStack = new Stack<int>();
            nodeStack.Push(root);
            sumStack.Push(sum);
            while(nodeStack.Count != 0)
            {
                var node = nodeStack.Pop();
                int s = sumStack.Pop() - node.val;
                if(node.left == null && node.right == null && s == 0) 
                {  
                    IList<int> path = new List<int>();
                    // Find path using parents
                    while(node != null)
                    {
                        path.Insert(0, node.val);
                        TreeNode par;
                        if(parent.TryGetValue(node, out par))
                        {
                            node = par;
                        }
                        else
                        {
                            node = null;
                        }
                    } 
                    
                    res.Add(path);
                }
                else
                {
                    if(node.left != null)
                    {
                        nodeStack.Push(node.left);
                        sumStack.Push(s);
                        parent.Add(node.left, node);
                    }
                    if(node.right != null)
                    {
                        nodeStack.Push(node.right);
                        sumStack.Push(s);
                        parent.Add(node.right, node);
                    }
                }
            }            
        }
        
        return res;
    }

Log in to reply
 

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