数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时装研究
法律研究C++ 中的相等树分区
假设我们有一棵包含 n 个节点的二叉树，我们的任务是检查是否可以将树划分为两棵树，在原始树上删除恰好一条边后，这两棵树的值的总和相等。
因此，如果输入如下
那么输出将为真。
要解决这个问题，我们将遵循以下步骤 −
定义一个栈 st
定义一个函数 solve()，它将采用节点，
如果节点为 null，则 −
返回 0
leftSum := solve（节点的左子树）
rightSum := solve（节点的右子树）
curr := 节点的值 + 左子树的和 + 右子树的和
将 curr 插入到 st
返回 curr
从主方法执行以下操作 −
solve（根节点）
totalSum := st 栈顶的元素
从 st 删除元素
只要 (st 不为空)，执行 −
x := st 栈顶的元素
从 st 删除元素
y := totalSum - 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
更新于:16-11-2020
369 次浏览
广告