题解 | #二叉树中是否存在节点和为指定值的路径#

采用递归遍历二叉树的路径节点，同时计算二叉树路径节点的数字之和，当到达叶子节点且路径的数字之和等于 sum 则说明二叉树中存在节点和为指定值的路径

算法步骤：

1、特殊情况：当二叉树为空，则返回 false

2、遍历根节点的左右子树，记录根节点的数字之和 res

当节点的左右子树均为空，且 res == sum，则返回 true

3、递归 该节点的左右子树，做上述计算

Python版本

class Solution:
    def hasPathSum(self , root , sum ):
        # write code here
        def preOrder(root, res):
            if not root:
                return False
            # 计算节点数字之和
            res += root.val
            if not root.left and not root.right and res == sum:
                return True
            # 递归左右子树
            return preOrder(root.left, res)&nbs***bsp;preOrder(root.right, res)
        return False if not root else preOrder(root, 0)

复杂度分析：

时间复杂度 O(N) ： N 为二叉树的节点数，最差的情况递归所有节点。
空间复杂度 O(1) ： 常数级变量空间

算法思想二：深度优先遍历+回溯

解题思路：

1、首先，深度优点遍历来说，先写上一个回溯 if (curNode == null) { return false; }，这表示递归至最深层开始回溯，至于为什么 return false 后面再讲
2、每次进入函数时，将 sum 减去当前节点的权重(curNode.val)，当 sum 减到零时，说明目标路径存在，另外我们的目标是到叶子节点停止，叶子节点的条件是 curNode.left == null && curNode.right == null，所以说当 if (curNode.left == null && curNode.right == null && target == 0) ，我们返回 true 表示找到目标路径
3、深度遍历的分支：对于当前节点 curNode 有两个分支，这两个分支都有可能成为目标路径，所以深度优先遍历的写法为 return dfs(curNode.left, target) || dfs(curNode.right, target);
4、现在来谈谈为什么回溯时需要返回 false，因为当 curNode 为叶子节点时，并且 sum == 0 时，我们已经返回了 true，剩下的情况就是 curNode 不是叶子节点或者路径值不为 target，所应该返回 false

图解：

JAVA版本

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if (root == null) {
            return false;
        }
        // 深度优先遍历
        return dfs(root, sum);
    }
    
    private boolean dfs(TreeNode curNode, int target) {
        // 目标路径不存在，开始回溯
        if (curNode == null) {
            return false;
        }
        // 更新目标值
        target -= curNode.val;
        // 当当前节点为叶子节点并且目标路径存在时，返回 true
        if (curNode.left == null && curNode.right == null && target == 0) {
            return true;
        }
        // 对左右分支进行 dfs
        return dfs(curNode.left, target) || dfs(curNode.right, target);
    }
}

复杂度分析：

时间复杂度 O(N) ： N 为二叉树的节点数，最差的情况递归所有节点。
空间复杂度 O(1) ：不需要额外空间