[Leetcode] 1448. Count Good Nodes in Binary Tree (C++)

https://leetcode.com/problems/count-good-nodes-in-binary-tree/

Count Good Nodes in Binary Tree - LeetCode

[풀이]

 

1. 재귀를 이용해서 이진트리의 모든 노드들을 순회한다.

2. 파라미터 v는 현재 node의 부모 node들의 value 중에 가장 큰 value를 의미한다.

3. 현재 노드의 value가 v보다 크면 return 값에 1을 더해 주어 결과값에 추가될 수 있도록 한다.

4. root는 무조건 추가되어야 하므로 main에서 -100000을 v에 넣어준다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

	int search(TreeNode* node, int v) {

		if (node == nullptr) return 0;
 
		int ret = 0;
		int cur_max = v;
		if (node->val >= v) {
			cur_max = node->val;
			ret++;
		}
		ret += search(node->left,  cur_max);
		ret += search(node->right, cur_max);

		return ret;
	}

	int goodNodes(TreeNode* root) {
		return search(root, -100000);
	}
};

https://github.com/has2/Algorithm/blob/master/leetcode/1448.cpp