聊聊每日算法之路徑總和
本文轉(zhuǎn)載自微信公眾號(hào)「三分鐘學(xué)前端」，作者sisterAn。轉(zhuǎn)載本文請(qǐng)聯(lián)系三分鐘學(xué)前端公眾號(hào)。
關(guān)于樹基礎(chǔ)看這里：適合初學(xué)者的樹
給定一個(gè)二叉樹和一個(gè)目標(biāo)和，判斷該樹中是否存在根節(jié)點(diǎn)到葉子節(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 1
返回 true , 因?yàn)榇嬖谀繕?biāo)和為 22 的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑 5->4->11->2。
解題思路：
只需要遍歷整棵樹
如果當(dāng)前節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，遞歸它的所有子節(jié)點(diǎn)，傳遞的參數(shù)就是 sum 減去當(dāng)前的節(jié)點(diǎn)值;
如果當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)，判斷參數(shù) sum 是否等于當(dāng)前節(jié)點(diǎn)值，如果相等就返回 true，否則返回 false。
代碼實(shí)現(xiàn)：
- var hasPathSum = function(root, sum) {
- // 根節(jié)點(diǎn)為空
- if (root === null) return false;
- // 葉節(jié)點(diǎn) 同時(shí) sum 參數(shù)等于葉節(jié)點(diǎn)值
- if (root.left === null && root.right === null) return root.val === sum;
- // 總和減去當(dāng)前值，并遞歸
- sum = sum - root.val
- return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
- };
解題思路：
只需要遍歷整棵樹
- 如果當(dāng)前節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，遞歸它的所有子節(jié)點(diǎn)，傳遞的參數(shù)就是 sum 減去當(dāng)前的節(jié)點(diǎn)值;
- 如果當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)，判斷參數(shù) sum 是否等于當(dāng)前節(jié)點(diǎn)值，如果相等就返回 true，否則返回 false。
代碼實(shí)現(xiàn)：
- var hasPathSum = function(root, sum) {
- // 根節(jié)點(diǎn)為空
- if (root === null) return false;
- // 葉節(jié)點(diǎn) 同時(shí) sum 參數(shù)等于葉節(jié)點(diǎn)值
- if (root.left === null && root.right === null) return root.val === sum;
- // 總和減去當(dāng)前值，并遞歸
- sum = sum - root.val
- return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
- };
leetcode：https://leetcode-cn.com/problems/path-sum/solution/javascript-lu-jing-zong-he-by-user7746o/
