資料結構
網路
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 次瀏覽
廣告