路徑總和

力扣題目鏈接

題目描述

給你二叉樹的根節點 root 和一個表示目標和的整數 targetSum 。判斷該樹中是否存在 根節點到葉子節點 的路徑，這條路徑上所有節點值相加等于目標和 targetSum 。如果存在，返回 true ；否則，返回 false 。

葉子節點 是指沒有子節點的節點。

解題思路

這里仍然是采用迭代的方式來解決這道題目，每次判斷當前節點是不是葉子節點的同時判斷該節點的值是否等于目標值，如果相等則返回true，如果不滿足就減去當前節點值然后判斷左右子樹是否存在滿足該條件。

題解

class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {if(root == NULL){return false;}if(!root->left && !root->right && root->val == targetSum) {return true;}return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);}
};

總結

本質就是迭代取遍歷二叉樹，但是把思維轉換成目標值減去節點值最終在葉子節點處等于0即可。