สมมติว่าเรามีไบนารีทรีที่มี n โหนด หน้าที่ของเราคือตรวจสอบว่าเป็นไปได้หรือไม่ที่จะแบ่งต้นไม้ออกเป็นสองต้นซึ่งมีผลรวมของค่าเท่ากันหลังจากลบขอบเดียวบนทรีเดิม
ดังนั้นหากอินพุตเป็นแบบ
แล้วผลลัพธ์จะเป็นจริง
-
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดหนึ่งสแต็ก st
-
กำหนดฟังก์ชัน Solve() ซึ่งจะใช้โหนด
-
ถ้าโหนดเป็นโมฆะ −
-
คืนค่า 0
-
-
leftSum :=แก้ (ซ้ายของโหนด)
-
rightSum :=แก้ (ทางขวาของโหนด)
-
curr :=val + leftSum + rightSum ของโหนด
-
ใส่ curr ลงใน st
-
ผลตอบแทนสกุลเงิน
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
แก้(ราก)
-
TotalSum :=องค์ประกอบด้านบนของ st
-
ลบองค์ประกอบออกจาก st
-
ในขณะที่ (ไม่ใช่ st ว่างเปล่า) ทำ -
-
x :=องค์ประกอบด้านบนของ st
-
ลบองค์ประกอบออกจาก st
-
y :=ผลรวมทั้งหมด - x
-
ถ้า x เท่ากับ y แล้ว −
-
คืนความจริง
-
-
-
คืนค่าเท็จ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#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:
stack <int> st;
int solve(TreeNode* node){
if (!node)
return 0;
int leftSum = solve(node->left);
int rightSum = solve(node->right);
int curr = node->val + leftSum + rightSum;
st.push(curr);
return curr;
}
bool checkEqualTree(TreeNode* root) {
solve(root);
int totalSum = st.top();
st.pop();
while (!st.empty()) {
int x = st.top();
st.pop();
int y = totalSum - x;
if (x == y)
return true;
}
return false;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(5);
root->left = new TreeNode(10);
root->right = new TreeNode(10);
root->right->left = new TreeNode(2);
root->right->right = new TreeNode(3);
cout<<(ob.checkEqualTree(root));
} อินพุต
TreeNode *root = new TreeNode(5); root->left = new TreeNode(10); root->right = new TreeNode(10); root->right->left = new TreeNode(2); root->right->right = new TreeNode(3);
ผลลัพธ์
1
