題目

給你一棵根為 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" 比它大。

示例 3：輸入：root = [1] 輸出：1

解釋：根節點是好節點。

提示：二叉樹中節點數目範圍是 [1, 10^5] 。

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

解題思路分析

1、遞迴；時間複雜度O(n)，空間複雜度O(log(n))

func goodNodes(root *TreeNode) int {	maxValue := math.MinInt32	return dfs(root, maxValue)}func dfs(root *TreeNode, maxValue int) int {	if root == nil {		return 0	}	if root.Val >= maxValue {		return dfs(root.Left, root.Val) + dfs(root.Right, root.Val) + 1	}	return dfs(root.Left, maxValue) + dfs(root.Right, maxValue)}

總結

Medium題目，二叉樹採用常規遞迴方法解題