数据结构
网络
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 次查看
广告