資訊專欄INFORMATION COLUMN
摘要：題目地址題目描述給定一個二叉樹和一個目標(biāo)和，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑。說明葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。示例給定如下二叉樹，以及目標(biāo)和，返回解答遞歸。以的右子樹為根并且和為的路徑加上若該路徑存在。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
給定一個二叉樹和一個目標(biāo)和，找到所有從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑總和等于給定目標(biāo)和的路徑。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
給定如下二叉樹，以及目標(biāo)和 sum = 22，
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
解答：
遞歸。求以root為根并且和為sum的路徑等于。
1root為空，那么為空(不存在這個路徑)。
2root為葉節(jié)點(diǎn),并且sum等于root.val，返回root這個單節(jié)點(diǎn)路徑。
3以root的左子樹為根并且和為sum-root.val的路徑加上root（若該路徑存在）。
4以root的右子樹為根并且和為sum-root.val的路徑加上root（若該路徑存在）。
java ac代碼：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List> pathSum(TreeNode root, int sum) {
List>ans = new ArrayList(100);
if(root == null)return ans;
if(root.left == null && root.right == null && sum == root.val)
{
List t = new LinkedList();
t.add(root.val);
ans.add(t);
return ans;
}
List>t1 = pathSum(root.left,sum-root.val);
List>t2 = pathSum(root.right,sum-root.val);
if(t1.size() > 0)
{
for(int i = 0;i < t1.size();i++)
{
LinkedListt = (LinkedList)t1.get(i);
t.addFirst(root.val);
ans.add(t);
}
}
if(t2.size() > 0)
{
for(int i = 0;i < t2.size();i++)
{
LinkedListt = (LinkedList)t2.get(i);
t.addFirst(root.val);
ans.add(t);
}
}
return ans;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/73599.html
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。因此使用一個數(shù)組代表每個節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對于一個具有樹特征的無向圖，我們可選擇任何一個節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個人主頁：應(yīng)無所住而生...
摘要：對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結(jié)束坐標(biāo)。可以射出的弓箭的數(shù)量沒有限制。弓箭一旦被射出之后，可以無限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。解答這是一道區(qū)間覆蓋問題，不太好說清楚，利用模板即可。 題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方...
摘要：有效二叉搜索樹定義如下節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
閱讀 1385·2021-11-22 09:34
閱讀 2591·2021-11-12 10:36
閱讀 1124·2021-11-11 16:55
閱讀 2337·2020-06-22 14:43
閱讀 1477·2019-08-30 15:55
閱讀 1988·2019-08-30 15:53
閱讀 1775·2019-08-30 10:50
閱讀 1231·2019-08-29 12:15
