讨论/《二叉树》 - 路径总和/
《二叉树》 - 路径总和

解题思路

没有看题解自己直接想到的是用累加法,后面看了题解才发现用减法更加灵活,不过大致思路都是差不多的,
递归法,从根节点开始,如果根节点为null,直接返回false,每次累加一个节点的值,
如果到了叶子节点且累加的和等于targetSum,则返回true,
递归返回左右子树的累加值,只要有一边符合就返回true,否则false。
基础差想了半个小时才想出来。。。

public boolean hasPathSum(TreeNode root, int targetSum) {
    return hasPathSumHelper(root, 0, targetSum);
}

public boolean hasPathSumHelper(TreeNode root, int a, int targetSum) {
    // 节点为null直接返回false
    if(root == null) return false;
    //累加节点值
    a += root.val;
    // 到叶子节点值相等则返回false
    // 也可以改成
    //if(root.left == null && root.right == null) return a == targetSum;
    if(root.left == null && root.right == null && a == targetSum) return true;
    //递归遍历左子树右子树
    return hasPathSumHelper(root.left, a, targetSum) || hasPathSumHelper(root.right, a, targetSum);
}

二叉树.png

1
展开全部 22 讨论