?LeetCode刷題實(shí)戰(zhàn)298：二叉樹(shù)最長(zhǎng)連續(xù)序列
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections .
The longest consecutive path need to be from parent to child (cannot be the reverse).
示例
解題
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void helper(TreeNode* root,int count,int& max_count){
if(root==NULL){//終止條件
return;
}
//若左結(jié)點(diǎn)不為空，則可以接著遍歷
if(root->left){
//若左結(jié)點(diǎn)和根節(jié)點(diǎn)的值的關(guān)系滿足連續(xù)，則調(diào)整長(zhǎng)度
if(root->val+1==root->left->val){
max_count=max(max_count,count+1);
helper(root->left,count+1,max_count);
}
else{
//否則將長(zhǎng)度重新置為1調(diào)整
helper(root->left,1,max_count);
}
}
//若右結(jié)點(diǎn)和根節(jié)點(diǎn)的值的關(guān)系滿足連續(xù)，則調(diào)整長(zhǎng)度
if(root->right){
if(root->val+1==root->right->val){
max_count=max(max_count,count+1);
helper(root->right,count+1,max_count);
}
else{
//否則將長(zhǎng)度重新置為1進(jìn)行統(tǒng)計(jì)
helper(root->right,1,max_count);
}
}
}
int longestConsecutive(TreeNode* root) {
if(root==NULL){
return 0;
}
int max_count=1;//初始長(zhǎng)度
helper(root,1,max_count);
return max_count;
}
};