C++ 中的二叉树最长连续序列
c++server side programmingprogramming
假设我们有一棵二叉树；我们必须检查是否可以找到最长连续序列路径的长度。如果该路径指的是从某个起始节点到树中沿父子连接的任何节点的任何节点序列。最长的连续路径需要从父节点到子节点，而不是反向。
因此，如果输入如下，
则输出将为 3，因为最长的连续序列路径为 3-4-5，因此返回 3。
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数solveUtil()，它将使用node、prev、len将其初始化为1，
如果node为空，则 −
return
如果 prev + 1 与节点的 val 相同，则 −
(将 len 增加 1)
ans := ans 和 len 的最大值
solveUtil(left of node, val of node, len)
solveUtil(right of node, val of node, len)
否则
solveUtil(left of node, val of node, 1)
solveUtil(right of node, val of node, 1)
定义一个函数solve()，它将采用A，
ans := 1
solveUtil(A, -infinity)
return ans
从 main 方法执行以下操作 −
如果 root 为 null，则−
return 0
return 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
