题目如下:
Given a binary tree
root
, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.Return the number of good nodes in the binary tree.
Example 1:
Input: root = [3,1,4,3,null,1,5] Output: 4 Explanation: Nodes in blue are good. Root Node (3) is always a good node. Node 4 -> (3,4) is the maximum value in the path starting from the root. Node 5 -> (3,4,5) is the maximum value in the path Node 3 -> (3,1,3) is the maximum value in the path.Example 2:
Input: root = [3,3,null,4,2] Output: 3 Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.Example 3:
Input: root = [1] Output: 1 Explanation: Root is considered as good.Constraints:
- The number of nodes in the binary tree is in the range
[1, 10^5]
.- Each node's value is between
[-10^4, 10^4]
.
解题思路:遍历树,记录当前路径出现过的最大值,与到达的节点比对即可。
代码如下:
# Definition for a binary tree node. class TreeNode(object): def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution(object): def goodNodes(self, root): """ :type root: TreeNode :rtype: int """ dic = {} def recursive(node,num,max_val): if max_val <= node.val: max_val = node.val dic[num] = 1 if node.left != None: recursive(node.left,num*2,max_val) if node.right != None: recursive(node.right,num*2+1,max_val) dic[1] = 1 recursive(root,1,root.val) return len(dic)