题解 | #二叉树中和为某一值的路径(一)#

采用二叉树的先序遍历，在叶子结点判断数字和是否相等即可，需要注意的是测试数据里，如果根结点的值等于数字和，是不算一条路径的，所以需要进行排除；而且题目只要求找到一条路径，所以可以假如左子树已经找到路径，那么右子树就不需要找了，可以进行剪枝。

时间复杂度最慢O(N)，平均复杂度小于O(N)

空间复杂度O(1)

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        return root == null || root.val == sum && (root.left != null || root.right != null)? false : preTravelTree(root, sum, 0);
    }
    
    public boolean preTravelTree(TreeNode t, int sum, int count){
        if(t == null)
            return sum == count;
        count += t.val;
        return preTravelTree(t.left, sum, count) ? true : preTravelTree(t.right, sum, count);
    }
}