資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中二叉樹中兩個葉子節點之間的最小和路徑
問題陳述
給定一棵二叉樹，其中每個節點元素都包含一個數字。任務是找到從一個葉子節點到另一個葉子節點的最小可能和。
示例
在上面的樹中，最小的子路徑如下：-6：(-4) + 3 + 2 + (-8) + 1
演算法
這個想法是在遞迴呼叫中保持兩個值：
- 當前節點下的子樹從根到葉子的最小路徑和
- 葉節點之間的最小路徑和
- 對於每個訪問過的節點 X，我們必須在 X 的左右子樹中找到從根到葉子的最小和。然後將這兩個值與 X 的資料相加，並將和與當前最小路徑和進行比較
示例
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
int data;
struct node *left;
struct node *right;
} node;
node *newNode(int data) {
node *n = new node;
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}
int getMinPath(node *root, int &result) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return root->data;
}
int leftSum = getMinPath(root->left, result);
int rightSum = getMinPath(root->right, result);
if (root->left && root->right) {
result = min(result, root->data + leftSum + rightSum);
return min(root->data + leftSum, root->data + rightSum);
}
if (root->left == NULL) {
return root->data + rightSum;
} else {
return root->data + leftSum;
}
}
int getMinPath(node *root) {
int result = INT_MAX;
getMinPath(root, result);
return result;
}
node *createTree() {
node *root = newNode(2);
root->left = newNode(3);
root->right = newNode(-8);
root->left->left = newNode(5);
root->left->right = newNode(-4);
root->right->left = newNode(1);
root->right->right = newNode(10);
return root;
}
int main() {
node *root = createTree();
cout << "Minimum sum path = " << getMinPath(root) << endl;
return 0;
}編譯並執行上面的程式後，它會生成以下輸出：
輸出
Minimum sum path = -6
更新於：2019 年 12 月 20 日
167 次瀏覽
廣告