สมมติว่าเรามีไบนารีทรี เราต้องหาผลรวมของใบไม้ที่ถูกต้องทั้งหมดในไบนารีทรีที่กำหนด
ดังนั้นหากอินพุตเป็นแบบ
จากนั้นผลลัพธ์จะเป็น 17 เนื่องจากมีใบทางขวาสองใบในไบนารีทรี โดยมีค่า 7 และ 10 ตามลำดับ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน dfs() สิ่งนี้จะรับโหนด เพิ่ม
-
ถ้าโหนดเป็นโมฆะ −
-
กลับ
-
-
หากด้านซ้ายของโหนดเป็นโมฆะและด้านขวาของโหนดเป็นโมฆะและการบวกไม่ใช่ศูนย์ −
-
ret :=ret + val ของโหนด
-
-
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
