C++에서 가장 깊은 노드의 합을 찾는 프로그램

<시간/>

이진 트리가 있다고 가정합니다. 우리는 가장 깊은 잎의 값의 합을 찾아야 합니다. 트리가 다음과 같다면 -

그러면 출력은 11이 됩니다.

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

맵 정의 m 및 maxDepth
재귀 메서드 solve()를 정의하면 노드와 레벨이 사용되며 초기 레벨은 0입니다.
노드가 없으면 반환
maxDepth :=레벨 및 maxDepth의 최대값
노드의 값만큼 m[레벨] 증가
해결(노드 왼쪽, 레벨 + 1)
해결(노드 오른쪽, 레벨 + 1)
기본 방법에서 maxDepth :=0으로 설정한 다음 solve(root, 0)
m[최대 깊이]
반환

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

예시

#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 maxDepth;
   map <int, int> m;
   void solve(TreeNode* node, int level = 0){
      if(!node)return;
      maxDepth = max(level, maxDepth);
      m[level] += node->val;
      solve(node->left, level + 1);
      solve(node->right, level + 1);
   }
   int deepestLeavesSum(TreeNode* root) {
      maxDepth = 0;
      m.clear();
      solve(root);
      return m[maxDepth];
   }
};
main(){
   TreeNode *root = new TreeNode(1);
   root−>left = new TreeNode(2);
   root−>right = new TreeNode(3);
   root−>left−>left = new TreeNode(4);
   root−>left−>right = new TreeNode(5);
   root−>right−>right = new TreeNode(6);
   root−>right−>right−>right = new TreeNode(4);
   root−>left−>left−>left = new TreeNode(7);
   Solution ob;
   cout << (ob.deepestLeavesSum(root));
}

입력

TreeNode *root = new TreeNode(1);
root−>left = new TreeNode(2);
root−>right = new TreeNode(3);
root−>left−>left = new TreeNode(4);
root−>left−>right = new TreeNode(5);
root−>right−>right = new TreeNode(6);
root−>right−>right−>right = new TreeNode(4);
root−>left−>left−>left = new TreeNode(7);