資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢樹中最大的子樹和
在這個問題中，我們給定一棵二叉樹。我們的任務是找到樹中最大的子樹和。
問題描述：二叉樹包含正值和負值。我們需要找到節點和最大的子樹。
讓我們舉個例子來理解這個問題，
輸出：13
解釋：
左子樹的和為 7
右子樹的和為 1
樹的和為 13
解決方案方法
為了解決這個問題，我們將進行後序遍歷。計算左子樹和右子樹的節點和。對於當前節點，檢查當前節點的節點和是否大於左子樹或右子樹的和。對於每個節點，從葉子到根找到最大和。
程式說明我們解決方案的工作原理，
示例
#include <iostream>
using namespace std;
struct Node {
int key;
Node *left, *right;
};
Node* newNode(int key) {
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
int calcSumTreeSumRec(Node* root, int& ans) {
if (root == NULL)
return 0;
int currSum = root->key + calcSumTreeSumRec(root->left, ans)+ calcSumTreeSumRec(root->right, ans);
ans = max(ans, currSum);
return currSum;
}
int calcMaxSubTreeSum(Node* root)
{
if (root == NULL)
return 0;
int ans = -100;
calcSumTreeSumRec(root, ans);
return ans;
}
int main() {
Node* root = newNode(5);
root->left = newNode(-4);
root->right = newNode(4);
root->left->left = newNode(3);
root->left->right = newNode(8);
root->right->left = newNode(-5);
root->right->right = newNode(2);
cout<<"The largest subtree sum is "<<calcMaxSubTreeSum(root);
return 0;
}輸出
The largest subtree sum is 13
更新於：2021-01-25
311 次檢視
廣告