經典筆試題: 二叉樹中和為某一值的路徑(路徑總和)
微信搜一搜:
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請你幫兩件事幫忙一下:
-
star支援一下, 您的肯定是我在平臺創作的源源動力。
-
微信搜尋「bigsai」,關注我的公眾號,不僅免費送你電子書,我還會第一時間在公眾號分享知識技術。加我還可拉你進力扣打卡群一起打卡LeetCode。
記得關注、咱們下次再見!
本文同步分享在 部落格“Big sai”(CSDN)。
如有侵權,請聯絡 [email protected] 刪除。
本文參與“OSC源創計劃”,歡迎正在閱讀的你也加入,一起分享。
- 結合大學四年經驗,帶你揭祕高效自學Java的方法和路線(從認識、方法、反饋3個角度出發)
- 因為LRU設計效率太低被pass了
- 動態規劃,就這些最常見了!
- 刷題難,程式設計師如何玩轉力扣?
- 如何搞定力扣刷題?
- 什麼是字典樹
- 資料結構與演算法—棧詳解
- 520,花一夜給女神寫走迷宮遊戲
- 雙鏈表最詳細圖解
- 大數加減乘除,一文搞定!
- (阿里高頻筆試)大數加減乘除,一文徹底搞定
- 【手寫資料結構】雙鏈表最詳細圖解
- 經典筆試題: 二叉樹中和為某一值的路徑(路徑總和)
- 資料結構與演算法必知基礎知識
- 一文搞懂線性表(順序表、連結串列)
- LeetCode 90子集Ⅱ&91解碼方法
- 跳錶(SkipList)|會跳的連結串列真的非常diao
- 三本逆襲成為學霸碩士研究生
- 5張圖搞懂Java引用拷貝、淺拷貝、深拷貝
- 花五分鐘看這篇之前,你才發現你不懂RESTful