数据结构
网络
关系数据库管理系统(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 次浏览
广告