經典筆試題: 二叉樹中和為某一值的路徑(路徑總和)

微信搜一搜：bigsai
大家都在關注的刷題、學習數據結構和算法寶藏項目
關注回覆進羣即可加入力扣打卡羣，歡迎划水。

這兩題是相似問題，循序漸進。也是力扣和劍指offer的經典題。

路徑總和

題目描述(題目鏈接)
給你二叉樹的根節點 root 和一個表示目標和的整數 targetSum ，判斷該樹中是否存在 根節點到葉子節點 的路徑，這條路徑上所有節點值相加等於目標和 targetSum 。

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

示例 1：

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
輸出：true

示例 2：

輸入：root = [1,2,3], targetSum = 5
輸出：false

示例 3：

輸入：root = [1,2], targetSum = 0
輸出：false

提示：

樹中節點的數目在範圍 [0, 5000] 內
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

分析
對於這種判斷的，只要有一個滿足條件的即可，在遍歷路徑上肯定使用dfs遍歷。向下一層的時候就處理一下當前層的值，這樣有一個滿足的結果那麼就可以返回true。當然，這裏我就沒有剪枝，如果有正確結果的話也可停止遞歸判斷。

具體實現的代碼為：

/**
 * 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 boolean hasPathSum(TreeNode root, int targetSum) {
   
   
		if(root==null)
			return false;
		int value=targetSum-root.val;
		if(root.left==null&&root.right==null)
		{
   
   
			if(value==0)
				return true;
		}
		else {
   
   
			return hasPathSum(root.left,value)||hasPathSum(root.right, value);
		}
		return false;
    }
}

路徑總和Ⅱ

題目描述(題目鏈接)
給定一個二叉樹和一個目標和，找到所有從根節點到葉子節點路徑總和等於給定目標和的路徑。

説明: 葉子節點是指沒有子節點的節點。

示例:

給定如下二叉樹，以及目標和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

分析：

這個問題就是要求返回所有滿足要求的結果，和上題略有不同就是需要找到所有結果並且保存，保存結果的話我們就需要一個List<Integer>存儲遍歷的結果,而List<List<Integer>>用來存儲所有的結果，所以在遞歸回溯的過程中就需要藉助回溯的過程經過每一個狀態，滿足狀態的就將這個List複製到結果集中去，需要返回的時候還需要移除當前層加入的結果。

具體實現的代碼為：

/**
 * 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 {
   
   
    List<Integer> team = new ArrayList<Integer>();
	List<List<Integer>> value = new ArrayList<List<Integer>>();
	public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
   
   
	
		if (root == null)
			return value;
		team.add(root.val);
		targetSum-=root.val;
		if(targetSum==0&&root.left==null&&root.right==null)
		{
   
   
			value.add(new ArrayList<Integer>(team));
		}
		pathSum(root.left, targetSum);
		pathSum(root.right, targetSum);
		team.remove(team.size()-1);
		return value;
    }
}

原創不易，bigsai請你幫兩件事幫忙一下:

1. star支持一下， 您的肯定是我在平台創作的源源動力。

2. 微信搜索「bigsai」，關注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術。加我還可拉你進力扣打卡羣一起打卡LeetCode。

記得關注、咱們下次再見！

本文同步分享在 博客“Big sai”（CSDN）。
如有侵權，請聯繫 [email protected] 刪除。
本文參與“OSC源創計劃”，歡迎正在閲讀的你也加入，一起分享。