資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中二叉樹的最大路徑和
在這個問題中，我們給定一個二叉樹，每個節點包含一個值。我們的任務是建立一個程式來找到二叉樹中兩個葉子節點之間的最大路徑和。
在這裡，我們必須找到從一個葉子節點到另一個葉子節點的路徑，該路徑將提供最大值的總和。這條最大和路徑可以/不可以包含根節點。
二叉樹是一種樹形資料結構，其中每個節點最多可以有兩個子節點。這些被稱為左孩子和右孩子。
示例 -
讓我們舉個例子來理解這個問題 -
輸入 - //二叉樹…
輸出 - 24
解釋 - 從葉子節點 2 到 9 的路徑將給出最大和，即 (2 + 5 + 6 -2 + 4 + 9) = 24
為了解決這個問題，我們將進行樹遍歷並存儲當前節點的左子樹/右子樹的最大和。此外，我們將找到迄今為止兩個葉子節點之間的最大路徑。
對於每個節點，我們將找到其子樹的最大可能的葉子到葉子的路徑。然後將其與整體最大路徑進行比較，並將兩個值的較大值儲存在全域性最大路徑和值中。
讓我們從我們的示例中檢視此解決方案以更好地理解解決方案 -
全域性最大和 = 6（對於路徑 2→5→-1）
現在我們將檢查是否將 6 作為根節點。
在左子樹中 -
到葉子節點的路徑的總和為 7 和 4。
最大值為 7（對於路徑 5→2）。
在右子樹中 -
到葉子節點的路徑的總和為 5，路徑為 (1→-3→7)，這是一種可能的方式。
不，葉子節點之間路徑的總和為 -
左子樹中葉子到根 (6) 的最大和 + 根 + 右子樹中葉子到根 (6) 的最大和 = 7 + 6 + 5 = 18。
與全域性最大路徑和 (6) 進行比較，新的全域性最大路徑和 = 18。
示例
查詢兩個葉子節點之間最大路徑和的程式 -
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node* left, *right;
};
struct Node* insertNode(int data){
struct Node* node = new(struct Node);
node->data = data;
node->left = node->right = NULL;
return (node);
}
int max(int a, int b)
{ return (a >= b)? a: b; }
int maxPathSumLeaf(struct Node *root, int &maxSum){
if (root==NULL) return 0;
if (!root->left && !root->right) return root->data;
int leftSubTree = maxPathSumLeaf(root->left, maxSum);
int rightSubTree = maxPathSumLeaf(root->right, maxSum);
if (root->left && root->right){
maxSum = max(maxSum, leftSubTree + rightSubTree + root->data);
return max(leftSubTree, rightSubTree) + root->data;
}
return (!root->left)? rightSubTree + root->data: leftSubTree + root->data;
}
int main(){
struct Node *root = insertNode(-2);
root->left = insertNode(6);
root->right = insertNode(4);
root->left->left = insertNode(5);
root->left->right = insertNode(1);
root->left->left->left = insertNode(2);
root->left->left->right = insertNode(-1);
root->left->right->left = insertNode(-3);
root->left->right->left->left = insertNode(7);
root->right->left = insertNode(9);
root->right->right = insertNode(3);
int maxSum = INT_MIN;
maxPathSumLeaf(root, maxSum);
cout<<"Max pathSum of between two leaf nodes for the given binary tree is "<<maxSum;
return 0;
}輸出
Max pathSum of between two leaf nodes for the given binary tree is 24
更新於: 2020年6月3日
224 次檢視
廣告