專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

馬上就要到五一了，今年的五一也是連休5天，很多人想利用這個時間回趟老家或者出去游玩，所以這段時間也是買票流量的高峰期。據12306顯示今天只能購買到4月30號的票，5月1號的票暫時還不能購買。

結果今天早上一條12306崩了的消息登上了熱搜，有不少網友反應今天早上買票的時候出現故障，網友也是非常憤怒，希望換程序員。實際上12306崩過也不是這一回了，沒辦法，流量太大，尤其是春節以及五一，十一這種長假，流量都會集中爆發。我剛試了下，沒有出現奔潰的現象，應該是修復了，有需要的現在可以購買了。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1448題：統計二叉樹中好節點的數目，難度是中等。

給你一棵根為 root 的二叉樹，請你返回二叉樹中好節點的數目。「好節點」X 定義為：從根到該節點 X 所經過的節點中，沒有任何節點的值大于 X 的值。

示例1：

輸入：root = [3,1,4,3,null,1,5] 輸出：4 解釋：圖中藍色節點為好節點。 根節點 (3) 永遠是個好節點。 節點 4 -> (3,4) 是路徑中的最大值。 節點 5 -> (3,4,5) 是路徑中的最大值。 節點 3 -> (3,1,3) 是路徑中的最大值。

示例2：

輸入：root = [3,3,null,4,2] 輸出：3 解釋：節點 2 -> (3, 3, 2) 不是好節點，因為 "3" 比它大。

• 二叉樹中節點數目范圍是 [1, 10^5] 。

• 每個節點權值的范圍是 [-10^4, 10^4] 。

問題分析

這題讓計算二叉樹中好節點的個數，所謂好節點就是從根節點開始到當前節點這條路徑上沒有比當前節點值大的節點，那么當前節點就是好節點。

我們直接使用dfs對二叉樹進行遍歷，需要記錄從根節點到當前節點這條路徑上的最大值。如果當前節點大于等于這個最大值，說明這條路徑上沒有比當前節點值大的節點，所以當前節點就是好節點，最后累加好節點的個數即可。

JAVA：

public int goodNodes(TreeNode root) {     return dfs(root, Integer.MIN_VALUE); } private int dfs(TreeNode root, int maxV) {     if (root == null)         return 0;     int left = dfs(root.left, Math.max(root.val, maxV));     int right = dfs(root.right, Math.max(root.val, maxV));     return left + right + (root.val < maxV ? 0 : 1); }

C++：

public:     int goodNodes(TreeNode *root) {         return dfs(root, INT_MIN);     }     int dfs(TreeNode *root, int maxV) {         if (root == nullptr)             return 0;         int left = dfs(root->left, max(root->val, maxV));         int right = dfs(root->right, max(root->val, maxV));         return left + right + (root->val < maxV ? 0 : 1);     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。