โปรแกรมหาผลรวมของโหนดที่ลึกที่สุดใน C++

สมมติว่าเรามีต้นไม้ไบนารี เราต้องหาผลรวมของค่าใบไม้ที่ลึกที่สุดของมัน ดังนั้นถ้าต้นไม้เป็นเหมือน −

จากนั้นผลลัพธ์จะเป็น 11

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดแผนที่ m และ maxDepth

• กำหนดวิธีการแบบเรียกซ้ำ Solvent() ซึ่งจะใช้โหนดและระดับ ระดับเริ่มต้นคือ 0

• หากไม่มีโหนดให้ส่งคืน

• maxDepth :=สูงสุดของระดับและ maxDepth

• เพิ่ม m[ระดับ] ตามค่าของโหนด

• แก้ (ด้านซ้ายของโหนด ระดับ + 1)

• แก้(ด้านขวาของโหนด ระดับ + 1)

• ในวิธีหลัก ตั้งค่า maxDepth :=0 จากนั้นจึงแก้ปัญหา (root, 0)

• กลับ m[maxDepth]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

ผลลัพธ์

11