C# iterative DFS Solution


  • 0
    S
    public class Solution {
        public bool HasPathSum(TreeNode root, int sum) {
            if (root == null) {
                return false;
            }
            
            Stack<TreeNode> s = new Stack<TreeNode>();
            // discovered nodes
            HashSet<TreeNode> d = new HashSet<TreeNode>();
            s.Push(root);
            
            int sum2 = 0;
            while (s.Count > 0) {
                TreeNode n = s.Peek();
                if (!d.Contains(n)) {
                    d.Add(n);
                    sum2 += n.val;
                    if (n.right != null) {
                        s.Push(n.right);
                    }
                    if (n.left != null) {
                        s.Push(n.left);
                    }
                    // check if leaf
                    if (n.left == null && n.right == null) {
                        if (sum2 == sum) {
                            return true;
                        }
                    }
                } else {
                    s.Pop();
                    if (n.right == null || d.Contains(n.right)) {
                        sum2 -= n.val;
                    }
                }
            }
            return false;
        }
    }

Log in to reply
 

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