Chương trình tìm tổng các lá bên phải của cây nhị phân trong C ++

Giả sử chúng ta có một cây nhị phân, chúng ta phải tìm tổng của tất cả các lá bên phải trong một cây nhị phân nhất định.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 17, vì có hai lá bên phải trong cây nhị phân, với các giá trị tương ứng là 7 và 10.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm dfs (), hàm này sẽ lấy nút, thêm,

• nếu nút là null, thì -

  • trở lại

• nếu bên trái của nút là null và bên phải của nút là null và thêm là khác 0, thì -

  • ret:=ret + val của nút

• dfs (bên trái của nút, sai)

• dfs (bên phải của nút, true)

• Từ phương thức chính, thực hiện như sau -

• ret:=0

• dfs (root, true)

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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);

Đầu ra

17