C++의 이진 트리에서 최대값 근 계산하기

바이너리 트리 루트가 있다고 가정합니다. 그 값이 모든 자손의 값보다 크거나 같은 노드의 수를 계산해야 합니다.

따라서 입력이 다음과 같으면

3을 제외한 모든 노드가 기준을 충족하므로 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

dfs() 함수를 정의하면 노드가 필요합니다.
노드가 null이 아니면 -
- 0 반환
l :=dfs(노드 왼쪽)
r :=dfs(노드 오른쪽)
노드의 val이>=l 및 r의 최대값이면 -
- (ret 1 증가)
x :=노드 val의 최대값, l 및 r
x를 반환
기본 방법에서 다음을 수행합니다.
ret :=0
dfs(루트)
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data) {
      val = data;
      left = NULL;
      right = NULL;
   }
};
class Solution {
   public:
   int ret;
   int dfs(TreeNode* node){
      if(!node)
         return 0;
      int l = dfs(node->left);
      int r = dfs(node->right);
      if(node->val >= max(l, r)) {
         ret++;
      }
      int x = max({node->val, l, r});
      return x;
   }
   int solve(TreeNode* root) {
      ret = 0;
      dfs(root);
      return ret;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(7);
   root->left = new TreeNode(4);
   root->right = new TreeNode(3);
   root->right->left = new TreeNode(7);
   root->right->right = new TreeNode(5);
   cout << (ob.solve(root));
}

입력

TreeNode *root = new TreeNode(7);
root->left = new TreeNode(4);
root->right = new TreeNode(3);
root->right->left = new TreeNode(7);
root->right->right = new TreeNode(5);