JZ84 二叉樹中和為某一值的路徑(三)
題目
給定一個二叉樹root和一個整數值 sum ，求該樹有多少路徑的的節點值之和等于 sum ，
1.該題路徑定義不需要從根節點開始，也不需要在葉子節點結束，但是一定是從父親節點往下到孩子節點
2.總節點數目為n
3.保證最后回傳的路徑個數在整形范圍內(即路徑個數小于231-1)
方法 非遞回層次遍歷
思路
演算法實作
既然要找所有路徑上節點和等于目標值的路徑個數，那我們肯定先找這樣的路徑起點啊，但是我們不知道起點究竟在哪里，
而且任意節點都有可能是起點，那我們就前序遍歷二叉樹的所有節點，每個節點都可以作為一次起點，即子樹的根節點，
具體做法：
step 1：每次將原樹中遇到的節點作為子樹的根節點送入dfs函式中查找有無路徑，如果該節點為空則回傳，
step 2：然后遞回遍歷這棵樹每個節點，每個節點都需要這樣操作，
step 3：在dfs函式中，也是往下遞回，遇到一個節點就將sum減去節點值再往下，
step 4：剩余的sum等于當前節點值則找到一種情況，
代碼
package mid.JZ84二叉樹中和為某一值的路徑3;
import java.util.*;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
/**
* 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
*
* @param root TreeNode類
* @param sum int整型
* @return int整型
*/
private int res = 0;
public int FindPath(TreeNode root, int sum) {
// write code here
if (root == null) return res;
//查詢以某結點為根的路徑數
dfs(root, sum);
//以其子結點為新根
FindPath(root.left, sum);
FindPath(root.right, sum);
return res;
}
public void dfs (TreeNode root, int sum) {
if (root == null) return;
//符合目標，res++
if (sum == root.val) res++;
//子節點繼續查找
dfs(root.left, sum - root.val);
dfs(root.right, sum - root.val);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/541251.html
標籤：其他