Find a path through root to leaf which's value is equal to specific sum value. And then return true or fasle.

Path_Sum.java

package wcy.leetcode.gist;

import java.util.LinkedList;

/**
 * Created by ChauyanWang on 12/20/14.
 */
public class Path_Sum {
    class TreeNode {
        TreeNode left;
        TreeNode right;
        int val;
        public TreeNode(int value) {val = value;}
    }
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        sum -= root.val;
        if(root.left == null && root.right == null)
            return sum == 0;
        else return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }

    public boolean hasPathSum(TreeNode root, int sum, int version) {
        if(root == null) return false;
        LinkedList<TreeNode> nodeList = new LinkedList<TreeNode>();
        LinkedList<Integer> valueList = new LinkedList<Integer>();
        nodeList.add(root);
        valueList.add(root.val);
        while(!nodeList.isEmpty()) {
            TreeNode node = nodeList.poll();
            int sumValue = valueList.poll();
            if(node.left == null && node.right == null && sumValue == sum)
                return true;
            if(node.left != null) {
                nodeList.add(node.left);
                valueList.add(sumValue + node.left.val);
            }
            if(node.right != null) {
                nodeList.add(node.right);
                valueList.add(sumValue + node.right.val);
            }
        }
        return false;
    }
}