मान लीजिए हमारे पास एक बाइनरी ट्री है हमें दिए गए बाइनरी ट्री में सभी दाएं पत्तों का योग ढूंढना है।
इसलिए, यदि इनपुट जैसा है
तो आउटपुट 17 होगा, क्योंकि बाइनरी ट्री में दो दाएं पत्ते हैं, जिनके मान 7 और 10 हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक फ़ंक्शन dfs() परिभाषित करें, यह नोड, add लेगा,
यदि नोड null है, तो -
लौटें
यदि नोड का left null है और नोड का right null है और add शून्येतर है, तो -
ret := ret + नोड का val
dfs(नोड का left, false)
dfs(नोड का right, true)
मुख्य विधि से, निम्न करें -
ret := 0
dfs(root, true)
ret लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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
