資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++實現二叉樹最長連續序列 II
假設我們有一個二叉樹；我們必須找到該二叉樹中最長連續路徑的長度。這裡的路徑可以是遞增的或遞減的。例如，[1,2,3,4] 和 [4,3,2,1] 都被視為有效路徑，但路徑 [1,2,4,3] 不是有效路徑。
否則，路徑可以在子節點-父節點-子節點序列中，不一定必須是父節點-子節點順序。
因此，如果輸入如下所示：
則輸出將為 3，因為最長的連續路徑將類似於 [1, 2, 3] 或 [3, 2, 1]。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 `solveUtil()`，它將接收節點作為引數；
如果節點為空，則：
返回 {0, 0}
左子節點 = `solveUtil`(節點的左子節點)
右子節點 = `solveUtil`(節點的右子節點)
定義一個名為 `temp` 的pair：{1,1}
如果存在左子節點並且左子節點的值等於節點值 + 1，則：
`temp.first` := `max(temp.first, 1 + left.first)`
`ans` := `max(ans, temp.first)`
如果存在右子節點並且右子節點的值等於節點值 + 1，則：
`temp.first` := `max(temp.first, 1 + right.first)`
`ans` := `max(ans, temp.first)`
如果存在左子節點並且左子節點的值等於節點值 - 1，則：
`temp.second` := `max(temp.second, 1 + left.second)`
`ans` := `max(ans, temp.second)`
如果存在右子節點並且右子節點的值等於節點值 - 1，則：
`temp.second` := `max(temp.second, 1 + right.second)`
`ans` := `max(ans, temp.second)`
`ans` := `max(ans, temp.first + temp.second - 1)`
返回 `temp`
在主方法中執行以下操作：
`ans` := 0
`solveUtil(root)`
返回 `ans`
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
int ans = 0;
pair<int, int> solveUtil(TreeNode* node){
if (!node) {
return { 0, 0 };
}
pair<int, int> left = solveUtil(node->left);
pair<int, int> right = solveUtil(node->right);
pair<int, int> temp = { 1, 1 };
if (node->left && node->left->val == node->val + 1) {
temp.first = max(temp.first, 1 + left.first);
ans = max(ans, temp.first);
}
if (node->right && node->right->val == node->val + 1) {
temp.first = max(temp.first, 1 + right.first);
ans = max(ans, temp.first);
}
if (node->left && node->left->val == node->val - 1) {
temp.second = max(temp.second, 1 + left.second);
ans = max(ans, temp.second);
}
if (node->right && node->right->val == node->val - 1) {
temp.second = max(temp.second, 1 + right.second);
ans = max(ans, temp.second);
}
ans = max({ ans, temp.first + temp.second - 1 });
return temp;
}
int longestConsecutive(TreeNode* root){
ans = 0;
solveUtil(root);
return ans;
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
cout << (ob.longestConsecutive(root));
}輸入
TreeNode *root = new TreeNode(2); root->left = new TreeNode(1); root->right = new TreeNode(3);
輸出
3
228 次瀏覽
