C++에서 이진 트리의 오른쪽 잎의 합을 찾는 프로그램

<시간/>

주어진 이진 트리에서 모든 오른쪽 잎의 합을 찾아야 하는 이진 트리가 있다고 가정합니다.

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

이진 트리에 두 개의 오른쪽 잎이 있고 값이 각각 7과 10이기 때문에 출력은 17이 됩니다.

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

dfs() 함수를 정의하면 노드, 추가,
가 필요합니다.
노드가 null이면 -
- 반환
노드의 왼쪽이 null이고 노드의 오른쪽이 null이고 add가 0이 아닌 경우 -
- ret :=ret + 노드의 val
dfs(노드 왼쪽, 거짓)
dfs(노드 오른쪽, 참)
기본 방법에서 다음을 수행하십시오 -
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 = 0;
   void dfs(TreeNode* node, bool add){
      if(!node)
      return ;
      if(!node−>left && !node->right && add){
         ret += node−>val;
      }
      dfs(node−>left, false);
      dfs(node−>right, true);
   }
   int solve(TreeNode* root) {
      ret = 0;
      dfs(root, true);
      return ret;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(3);
   root−>left = new TreeNode(9);
   root−>right = new TreeNode(10);
   root−>left−>left = new TreeNode(15);
   root−>left−>right = new TreeNode(7);
   cout << (ob.solve(root));
}

입력

TreeNode *root = new TreeNode(3);
root−>left = new TreeNode(9);
root−>right = new TreeNode(10);
root−>left−>left = new TreeNode(15);
root−>left−>right = new TreeNode(7);