描述
給定一個二叉樹root和一個值 sum ，判斷是否有從根節點到葉子節點的節點值之和等于 sum 的路徑，
1.該題路徑定義為從樹的根結點開始往下一直到葉子結點所經過的結點
2.葉子節點是指沒有子節點的節點
3.路徑只能從父節點到子節點，不能從子節點到父節點
4.總節點數目為n.
思路
按照前序遍歷遍歷接點，把每個節點的值都添加到count中，當走到葉子節點時，如果count == sum就回傳true，否則就回傳到父節點，并且將count的值減去剛剛加入進去的值，
代碼
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布爾型
*/
boolean res = false;
public boolean hasPathSum (TreeNode root, int sum) {
if(sum == 0 || root == null){
return false;
}
func(root,0,sum);
return res;
}
public void func(TreeNode root, int count,int sum){
if(res){
return;
}
count = count + root.val;
if(root.left != null && count != sum){
func (root.left,count,sum);
}
if(root.right != null && count != sum){
func (root.right,count,sum);
}
if(count == sum && root.left == null && root.right == null){
//標致位，說明該路徑已經找到了，
res = true;
return;
}else{
//走到葉子節點后，沒有找到就結束，回傳到父節點，
return;
}
}
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/375880.html
標籤：其他
下一篇：【藍橋杯】~C語言陣列排序