資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++實現的樹中最大和（不允許相鄰層）
在這個問題中，我們得到一個由正陣列成的二叉樹。我們的任務是建立一個程式，用C++查詢樹中不允許相鄰層的最大和。
程式碼描述
在這裡，我們將以這樣的方式找到樹節點的最大和：和中不包含來自樹中兩個相鄰層的節點。
讓我們來看一個例子來理解這個問題：
輸出
21
解釋
以根節點作為起始層，和 = 5 + 3 + 8 + 1 = 17。以根節點的子節點作為起始層，和 = 2 + 6 + 9 + 4 = 21。
解決方案方法
為了找到maxSum，一個條件是沒有相鄰元素。為此，我們將從根節點（第1層）獲取一個和集合，從子節點（第2層）獲取另一個和集合。下一個和節點將透過查詢孫子節點從當前節點提取。
為此，我們將遞迴地查詢maxSum值，然後從第1層或第2層開始的和的最大值將是結果maxSum。
示例
程式演示了我們解決方案的工作原理：
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* left, *right;
Node(int item){
data = item;
}
};
int getMaxSum(Node* root) ;
int findSumFromNode(Node* root){
if (root == NULL)
return 0;
int sum = root->data;
if (root->left != NULL){
sum += getMaxSum(root->left->left);
sum += getMaxSum(root->left->right);
}
if (root->right != NULL){
sum += getMaxSum(root->right->left);
sum += getMaxSum(root->right->right);
}
return sum;
}
int getMaxSum(Node* root){
if (root == NULL)
return 0;
return max(findSumFromNode(root), (findSumFromNode(root->left) + findSumFromNode(root->right)));
}
int main(){
Node* root = new Node(5);
root->left = new Node(2);
root->right = new Node(10);
root->left->left = new Node(4);
root->left->right = new Node(6);
root->right->right = new Node(9);
cout<<"The maximum sum from a tree with adjacent levels not allowed is "<<getMaxSum(root);
return 0;
}輸出
The maximum sum from a tree with adjacent levels not allowed is 24
更新於：2020年10月15日
瀏覽量 106 次
廣告