資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 實現二叉樹最長連續序列
假設我們有一個二叉樹；我們需要檢查是否可以找到最長連續序列路徑的長度。如果路徑指的是從某個起始節點到樹中任何節點的任何節點序列，沿著父子連線。最長的連續路徑需要遵循從父節點到子節點，而不是反過來。
因此，如果輸入如下所示：
則輸出為 3，因為最長連續序列路徑是 3-4-5，所以返回 3。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 `solveUtil()`，它將接收節點、前一個節點值 `prev` 和長度 `len`（初始化為 1）。
如果節點為空，則：
返回
如果 `prev + 1` 等於節點的值，則：
（將 `len` 增加 1）
`ans` := `ans` 和 `len` 的最大值
`solveUtil(節點的左子節點, 節點的值, len)`
`solveUtil(節點的右子節點, 節點的值, len)`
否則
`solveUtil(節點的左子節點, 節點的值, 1)`
`solveUtil(節點的右子節點, 節點的值, 1)`
定義一個函式 `solve()`，它將接收根節點 `A`。
`ans` := 1
`solveUtil(A, -infinity)`
返回 `ans`
從主方法執行以下操作：
如果根節點為空，則：
返回 0
返回 `solve(root)`
示例
讓我們來看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int< v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
int ans;
void solveUtil(TreeNode* node, int prev, int len = 1){
if (!node)
return;
if (prev + 1 == node->val) {
len++;
ans = max(ans, len);
solveUtil(node->left, node->val, len);
solveUtil(node->right, node->val, len);
}
else {
solveUtil(node->left, node->val, 1);
solveUtil(node->right, node->val, 1);
}
}
int solve(TreeNode* A){
ans = 1;
solveUtil(A, INT_MIN);
return ans;
}
int longestConsecutive(TreeNode* root){
if (!root)
return 0;
return solve(root);
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(1);
root->right = new TreeNode(3);
root->right->left = new TreeNode(2);
root->right->right = new TreeNode(4);
root->right->right->right = new TreeNode(5);
cout << (ob.longestConsecutive(root));
}輸入
TreeNode *root = new TreeNode(1); root->right = new TreeNode(3); root->right->left = new TreeNode(2); root->right->right = new TreeNode(4); root->right->right->right = new TreeNode(5);
輸出
3
更新於：2020年11月18日
145 次瀏覽
廣告