一、題目大意
給定一個二叉樹的根節點 root ，和一個整數 targetSum ，求該二叉樹里節點值之和等于 targetSum 的 路徑 的數目，
路徑 不需要從根節點開始，也不需要在葉子節點結束，但是路徑方向必須是向下的（只能從父節點到子節點），
示例 1：
輸入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
輸出：3
解釋：和等于 8 的路徑有 3 條，如圖所示，
示例 2：
輸入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
輸出：3
提示:
-
二叉樹的節點個數的范圍是 [0,1000]
-
-109 <= Node.val <= 109
-
-1000 <= targetSum <= 1000
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/path-sum-iii
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
雙層遞回實作，注意分情況考慮：1、如果選取該節點加入路徑，則之后必須繼續加入連續節點，或停止加入節點；2、如果不選取該節點加入路徑，則對其左右節點進行重新考慮，因此一個方便的方法是我們創建一個輔函式，專門用來計算連續加入節點的路徑，
三、解題方法
3.1 Java實作
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
return pathSumStartWithRoot(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
}
/**
* 注意，這里入參型別為long，否則通不過下面這個用例
* 這里root.val太大，遞回呼叫多了targetNum-root.val就會溢位整數型的最小值，把引數換成long即可
* [1000000000,1000000000,null,294967296,null,1000000000,null,1000000000,null,1000000000]
* 0
*/
int pathSumStartWithRoot(TreeNode root, long targetSum) {
if (root == null) {
return 0;
}
int count = root.val == targetSum ? 1 : 0;
count += pathSumStartWithRoot(root.left, targetSum - root.val);
count += pathSumStartWithRoot(root.right, targetSum - root.val);
return count;
}
}
四、總結小記
- 2022/9/8 求人不如求己
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/505948.html
標籤：其他