Count Good Nodes in Binary Tree
给一个二叉树, 求其中的good node的数量, 一个node被认为是good node,就是从root到它的path中没有比他大的.
求极值, 我用priority queue..只要遍历就可以了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int goodNodes(TreeNode* root, priority_queue <int> pq = priority_queue <int>()) { if(!root){ return 0; } if(pq.empty() || pq.top() <= root->val) { pq.push(root->val); return goodNodes(root->left, pq) + goodNodes(root->right, pq) + 1; } else{ pq.push(root->val); return goodNodes(root->left, pq) + goodNodes(root->right, pq); } } }; |