資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中二叉樹最大連續遞增路徑長度
假設我們有一個二叉樹；我們必須計算由連續遞增值節點組成的最長路徑的長度。每個節點將被視為長度為 1 的路徑。
因此，如果輸入類似於
則輸出將為 3，因為 (11, 12, 13) 是最大連續路徑。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 solve()，它將接收根節點、前一個數據、前一個長度作為引數。
- 如果根節點不為零，則：
- 返回前一個長度
- 當前資料 := 根節點的值
- 如果當前資料等於前一個數據 + 1，則：
- 返回 solve(根節點的左子節點, 當前資料, 前一個長度+1) 和 solve(根節點的右子節點, 當前資料, 前一個長度+1) 中的最大值
- 新路徑長度 := solve(根節點的左子節點, 當前資料, 1) 和 solve(根節點的右子節點, 當前資料, 1) 中的最大值
- 返回前一個長度和新路徑長度中的最大值
- 從主方法執行以下操作：
- 如果根節點等於 NULL，則：
- 返回 0
- 返回 solve(根節點, 根節點的值-1, 0)
示例 (C++)
讓我們看看以下實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
int solve(TreeNode *root, int prev_data, int prev_length){
if (!root)
return prev_length;
int cur_data = root->val;
if (cur_data == prev_data+1){
return max(solve(root->left, cur_data, prev_length+1), solve(root->right, cur_data, prev_length+1));
}
int newPathLen = max(solve(root->left, cur_data, 1), solve(root->right, cur_data, 1));
return max(prev_length, newPathLen);
}
int maxLen(TreeNode *root){
if (root == NULL)
return 0;
return solve(root, root->val-1, 0);
}
int main(){
TreeNode *root = new TreeNode(10);
root->left = new TreeNode(11);
root->right = new TreeNode(9);
root->left->left = new TreeNode(13);
root->left->right = new TreeNode(12);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(8);
cout << maxLen(root);
return 0;
}輸入
TreeNode *root = new TreeNode(10); root->left = new TreeNode(11); root->right = new TreeNode(9); root->left->left = new TreeNode(13); root->left->right = new TreeNode(12); root->right->left = new TreeNode(13); root->right->right = new TreeNode(8);
輸出
3
更新於: 2020-08-27
186 次瀏覽
廣告