給你一棵根為?root?的二叉樹，請(qǐng)你返回二叉樹中好節(jié)點(diǎn)的數(shù)目。
「好節(jié)點(diǎn)」X 定義為：從根到該節(jié)點(diǎn) X 所經(jīng)過的節(jié)點(diǎn)中，沒有任何節(jié)點(diǎn)的值大于 X 的值。
示例 1：
輸入：root = [3,1,4,3,null,1,5] 輸出：4 解釋：圖中藍(lán)色節(jié)點(diǎn)為好節(jié)點(diǎn)。 根節(jié)點(diǎn) (3) 永遠(yuǎn)是個(gè)好節(jié)點(diǎn)。 節(jié)點(diǎn) 4 -> (3,4) 是路徑中的最大值。 節(jié)點(diǎn) 5 -> (3,4,5) 是路徑中的最大值。 節(jié)點(diǎn) 3 -> (3,1,3) 是路徑中的最大值。
示例 2：
輸入：root = [3,3,null,4,2] 輸出：3 解釋：節(jié)點(diǎn) 2 -> (3, 3, 2) 不是好節(jié)點(diǎn)，因?yàn)?"3" 比它大。
示例 3：
輸入：root = [1] 輸出：1 解釋：根節(jié)點(diǎn)是好節(jié)點(diǎn)
提示：
- 二叉樹中節(jié)點(diǎn)數(shù)目范圍是?
[1, 10^5]?。 - 每個(gè)節(jié)點(diǎn)權(quán)值的范圍是?
[-10^4, 10^4]?。
思路：
樹的題目可以說百分之八十以上都是使用遞歸深搜的辦法。這個(gè)也是一個(gè)典型的dfs的題目。文章來源：http://www.zghlxwxcb.cn/news/detail-681552.html
往下遞歸的同時(shí)需要維護(hù)一個(gè)當(dāng)前路徑上的最大值，而ans的話，看個(gè)人喜好，我是將ans同步傳遞下去進(jìn)行更新。具體細(xì)節(jié)可以看看code。文章來源地址http://www.zghlxwxcb.cn/news/detail-681552.html
class Solution {
public int goodNodes(TreeNode root) {
int ans = 0;
int mmax = -100000; // 數(shù)據(jù)的最小值
ans = dfs(root, mmax, ans);
return ans;
}
public int dfs(TreeNode root, int mmax, int ans) {
if (mmax <= root.val) {
ans += 1; // 如果當(dāng)前節(jié)點(diǎn)大于最小值，則+1
mmax = root.val;
}
int left = ans, right = ans; // 初始化
if (root.left != null) left = dfs(root.left, mmax, ans);
if (root.right != null) right = dfs(root.right, mmax, ans);
ans = left + right - ans; // 這塊相當(dāng)于返回了左右節(jié)點(diǎn)（包含了當(dāng)前節(jié)點(diǎn)ans的所有好節(jié)點(diǎn)），這樣會(huì)導(dǎo)致ans多加了一次，所以要減掉
return ans;
}
}到了這里，關(guān)于每日一題：leetcode 1448 統(tǒng)計(jì)二叉樹中好節(jié)點(diǎn)的數(shù)目的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
