Giả sử chúng ta có một cây nhị phân với n nút, nhiệm vụ của chúng ta là kiểm tra xem liệu có thể phân chia cây thành hai cây có tổng giá trị bằng nhau sau khi xóa chính xác một cạnh trên cây ban đầu hay không.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là true.
-
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một ngăn xếp
-
Xác định một hàm giải quyết (), điều này sẽ lấy nút,
-
nếu nút là null, thì -
-
trả về 0
-
-
leftSum:=giải quyết (bên trái của nút)
-
rightSum:=giải quyết (bên phải của nút)
-
curr:=val + leftSum + rightSum của nút
-
chèn curr vào st
-
trả lại curr
-
Từ phương thức chính, hãy làm như sau -
-
giải quyết (root)
-
totalSum:=phần tử hàng đầu của st
-
xóa phần tử khỏi st
-
while (not st là trống), do -
-
x:=phần tử hàng đầu của st
-
xóa phần tử khỏi st
-
y:=totalSum - x
-
nếu x giống y thì -
-
trả về true
-
-
-
trả về false
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
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);
Đầu ra
1