描述

题目描述

给定一个二叉树和一个值sum ，判断是否有从根节点到叶子节点的节点值之和等于sum的路径，

示例

输入：{1,2},0
返回值：false

知识点：二叉树
难度：⭐⭐

题解

解题思路

二叉树的问题往往都能通过遍历和递归解决，只是递归相对遍历不好理解，但一旦掌握递归的诀窍，能节省很多行代码，也更好理解

方法一：递归&DFS

图解

算法流程：

• 定义递归函数功能：判断是否当前结点root为止的路径和为sum
• 每次递归都减掉经过的结点的值
• 当前结点是叶子结点，并且sum刚好为0，表明该路径和刚好为sum
• 返回时，保证能递归每个结点，且只需要有一条路径满足即可

Java 版本代码如下：

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        // 递归终止条件
        if (root == null)
            return false;
        // 每次递归都减掉经过的结点的值
        sum -= root.val;
        // 当前结点是叶子结点，并且sum刚好为0，表明该路径和刚好为sum
        if (sum == 0 && root.left == null && root.right == null)
            return true;
        // 保证能递归每个结点，且只需要有一条路径满足即可
        // 本质上是DFS深度优先遍历，只是由递归实现
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }
}

Python 版本代码如下：

class Solution:
    def hasPathSum(self , root , sum ):
        # 递归终止条件
        if root is None:
            return False
        def dfs(root,sum):
            if not root:
                return False
            # 当前结点是叶子结点，并且sum刚好为0，表明该路径和刚好为sum
            if root.left is None and root.right is None and sum==root.val:
                return True
            # 保证能递归每个结点，且只需要有一条路径满足即可
            else:
                # 每次递归都减掉经过的结点的值
                return dfs(root.left,sum-root.val) or dfs(root.right,sum-root.val)
        return dfs(root,sum)

复杂度分析：

时间复杂度 O(N)：最坏的i情况是递归每个结点，N为节点数
空间复杂度 O(1)：不需要额外空间

总结：二叉树相关的问题可以优先考虑递归方法解决