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

方法一（深度优先搜索）

1.题意整理

• 给定一颗二叉树以及一个值sum，二叉树中每个节点对应一个节点值。
• 判断二叉树中是否有从根节点到叶子节点的节点值之和等于sum的路径。

2.思路整理

可以利用深度优先搜索，遍历所有可能的路径，然后看某个路径的和是否等于sum，如果存在这样的路径，则直接返回true。

• 递归终止条件：当搜索完所有路径，即root为空，还没有找到合法路径，直接返回false。
• 递归如何传递：每次需要往左右子树方向递归，sum的值要减去当前节点值，如果遇到叶子节点，并且sum为0，说明路径合法，直接返回true。
• 递归的返回值：只要左子树或右子树不为空，则表示可以继续遍历，当前层返回true。

图解展示：

3.代码实现

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) {
        //如果为空，还没有找到合法的路径，直接返回false
        if(root==null) return false;
        //每遍历一个节点，sum减去对应节点值
        sum-=root.val;
        //如果遇到叶子节点，并且sum为0，说明路径合法，直接返回true
        if(root.left==null&&root.right==null&&sum==0){
            return true;
        } 
        //只要左子树或右子树不为空，则可以继续遍历
        return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
    }
    
}

4.复杂度分析

• 时间复杂度：需要遍历二叉树中所有节点，并且每个节点的访问次数不超过2，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：递归栈的深度为$lo{g}_{2}nlog\_2n$，当退化为链表时，深度为n，所以空间复杂度为$O(n)O(n)$。