摘要:計(jì)算從根到葉子節(jié)點(diǎn)生成的所有數(shù)字之和。說(shuō)明葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。代碼方法二,自頂向下搜索深度優(yōu)先搜索,搜索過(guò)程中維護(hù)一個(gè)當(dāng)前累加值,一旦搜索到葉子節(jié)點(diǎn),就將現(xiàn)在的當(dāng)前累加值加入結(jié)果中。
題目地址:
https://leetcode-cn.com/probl...
題目描述:
給定一個(gè)二叉樹(shù),它的每個(gè)結(jié)點(diǎn)都存放一個(gè) 0-9 的數(shù)字,每條從根到葉子節(jié)點(diǎn)的路徑都代表一個(gè)數(shù)字。 例如,從根到葉子節(jié)點(diǎn)路徑 1->2->3 代表數(shù)字 123。 計(jì)算從根到葉子節(jié)點(diǎn)生成的所有數(shù)字之和。 說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。 示例 1: 輸入: [1,2,3] 1 / 2 3 輸出: 25 解釋: 從根到葉子節(jié)點(diǎn)路徑 1->2 代表數(shù)字 12. 從根到葉子節(jié)點(diǎn)路徑 1->3 代表數(shù)字 13. 因此,數(shù)字總和 = 12 + 13 = 25. 示例 2: 輸入: [4,9,0,5,1] 4 / 9 0 / 5 1 輸出: 1026 解釋: 從根到葉子節(jié)點(diǎn)路徑 4->9->5 代表數(shù)字 495. 從根到葉子節(jié)點(diǎn)路徑 4->9->1 代表數(shù)字 491. 從根到葉子節(jié)點(diǎn)路徑 4->0 代表數(shù)字 40. 因此,數(shù)字總和 = 495 + 491 + 40 = 1026.
解答:
方法一,自底向上求出所有的路徑,然后把路徑求和。
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 int sumNumbers(TreeNode root) { if(root == null)return 0; Listlist = getList(root); int ans = 0; for(String s : list) ans += Integer.parseInt(s); return ans; } List getList(TreeNode root) { List ans = new ArrayList(); if(root == null) return ans; List t1 = getList(root.left); List t2 = getList(root.right); for(String s:t1) ans.add(root.val+s); for(String s:t2) ans.add(root.val+s); if(t1.size() == 0 && t2.size() == 0) ans.add(root.val+""); return ans; } }
方法二,自頂向下搜索(深度優(yōu)先搜索),搜索過(guò)程中維護(hù)一個(gè)當(dāng)前累加值,一旦搜索到葉子節(jié)點(diǎn),就將現(xiàn)在的當(dāng)前累加值加入結(jié)果中。這樣可以每個(gè)節(jié)點(diǎn)只訪問(wèn)一遍,并且沒(méi)有額外空間消耗。
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 int sumNumbers(TreeNode root) { dfs(root,0); return ans; } int ans = 0; void dfs(TreeNode root,int temp) { if(root == null) return; temp = temp*10+root.val; if(root.left == null && root.right == null) { ans += temp; return; } dfs(root.left,temp); dfs(root.right,temp); } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/74208.html
摘要:圖因此可以成為樹(shù),在所有可能的樹(shù)中,具有最小高度的樹(shù)被稱為最小高度樹(shù)。給出這樣的一個(gè)圖,寫出一個(gè)函數(shù)找到所有的最小高度樹(shù)并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度,若入度為就是葉子節(jié)點(diǎn)。 題目地址:https://leetcode-cn.com/probl...題目描述: 對(duì)于一個(gè)具有樹(shù)特征的無(wú)向圖,我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹(shù),在所有可能的樹(shù)中,具有最小...
摘要:關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板,終止條件,遞歸調(diào)用,邏輯處理。 ?作者簡(jiǎn)介:大家好,我是車神哥,府學(xué)路18號(hào)的車神? ?個(gè)人主頁(yè):應(yīng)無(wú)所住而生...
摘要:對(duì)于每個(gè)氣球,提供的輸入是水平方向上,氣球直徑的開(kāi)始和結(jié)束坐標(biāo)。可以射出的弓箭的數(shù)量沒(méi)有限制。弓箭一旦被射出之后,可以無(wú)限地前進(jìn)。我們想找到使得所有氣球全部被引爆,所需的弓箭的最小數(shù)量。解答這是一道區(qū)間覆蓋問(wèn)題,不太好說(shuō)清楚,利用模板即可。 題目地址:https://leetcode-cn.com/probl...題目描述:在二維空間中有許多球形的氣球。對(duì)于每個(gè)氣球,提供的輸入是水平方...
摘要:有效二叉搜索樹(shù)定義如下節(jié)點(diǎn)的左子樹(shù)只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。而我們二叉搜索樹(shù)保證了左子樹(shù)的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值,根節(jié)點(diǎn)的值均小于右子樹(shù)的值,因此中序遍歷以后得到的序列一定是升序序列。 ...
閱讀 2962·2021-10-18 13:33
閱讀 847·2019-08-30 14:20
閱讀 2633·2019-08-30 13:14
閱讀 2524·2019-08-29 18:38
閱讀 2892·2019-08-29 16:44
閱讀 1216·2019-08-29 15:23
閱讀 3491·2019-08-29 13:28
閱讀 1918·2019-08-28 18:00