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