C++ 中的二叉树最长连续序列 II
假设我们有一棵二叉树；我们必须找到该二叉树中最长连续路径的长度。这里的路径可以是递增的，也可以是递减的。因此，例如 [1,2,3,4] 和 [4,3,2,1] 都被视为有效路径，但路径 [1,2,4,3] 不是有效路径。
否则，路径可以按子-父-子顺序排列，不一定是父-子顺序。
因此，如果输入如下
那么输出将是 3，因为最长的连续路径将是 [1, 2, 3] 或 [3, 2, 1]。
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数solveUtil()，它将接受节点，
如果节点为空，则−
返回 { 0, 0
left =solveUtil(节点左侧)
left =solveUtil(节点右侧)
定义一对temp := {1,1
如果节点左侧存在并且节点左侧的值与节点值 + 1 相同，则−
temp.first := temp.first 和 1 + left.first 的最大值
ans := ans 和的最大值temp.first
如果节点的右侧存在，并且节点右侧的值与节点的值 + 1 相同，则 −
temp.first := temp.first 和 1 + right.first 的最大值
ans := ans 和 temp.first 的最大值
如果节点的左侧存在，并且节点左侧的值与节点的值 - 1 相同，则 −
temp.second := temp.second 和 1 + left.second 的最大值
ans := ans 和 temp.second 的最大值
如果节点的右侧存在，并且节点右侧的值与节点值 - 1 相同，然后 −
temp.second := temp.second 和 1 + right.second 的最大值
ans := ans 和 temp.second 的最大值
ans := { ans 和 temp.first + temp.second - 1 的最大值
返回 temp
从主方法执行以下操作 −
ans := 0
solveUtil(root)
return 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
