Accepted java solution. Iterative depth-first-search.


  • 2
    O
    public class Solution {
        public boolean hasPathSum(TreeNode root, int sum) {
        	if (root == null) {
        		return false;
        	}
        	Stack<TreeNode> stack = new Stack<TreeNode>();
        	TreeNode temp, last;
        	ArrayList<TreeNode> visited = new ArrayList<TreeNode>(); 
        	stack.push(root);
        	int checkSum = root.val, prevSum = 0;
        	while(!stack.isEmpty()) {
        		temp = stack.peek();
        		if (temp.left != null && !visited.contains(temp.left)) {
        			stack.push(temp.left);
        			visited.add(temp.left);
            		checkSum += temp.left.val;
        			continue;
        		}
        		if(temp.right != null && !visited.contains(temp.right)) {
            		checkSum += temp.right.val;
        			visited.add(temp.right);
        			stack.push(temp.right);
        			continue;
        		}
        		if (temp.left == null && temp.right == null && checkSum == sum) {
        			return true;
        		}
        		last = stack.pop();
        		checkSum -= last.val;
        	}
            return false;
        }
    }

Log in to reply
 

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