मान लीजिए कि हमारे पास एक बाइनरी ट्री है, तो हमें दिए गए बाइनरी ट्री में सभी दाएँ पत्तों का योग ज्ञात करना है।
तो, अगर इनपुट पसंद है
तब आउटपुट 17 होगा, क्योंकि बाइनरी ट्री में दो दाहिने पत्ते हैं, जिनका मान क्रमशः 7 और 10 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन dfs() को परिभाषित करें, यह नोड लेगा, जोड़ देगा,
-
यदि नोड शून्य है, तो -
-
वापसी
-
-
यदि नोड का बायां भाग शून्य है और नोड का दायां शून्य है और जोड़ गैर-शून्य है, तो -
-
रिट :=रिट + नोड का वैल
-
-
dfs (नोड के बाएँ, असत्य)
-
dfs (नोड का अधिकार, सत्य)
-
मुख्य विधि से, निम्न कार्य करें -
-
रिट:=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);
आउटपुट
17