題目
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).
For example,
1
\
3
/ \
2 4
\
5
Longest consecutive sequence path is 3-4-5, so return 3.
2
\
3
/
2
/
1
Longest consecutive sequence path is 2-3,not3-2-1, so return 2.
解題之法
class Solution {
public:
int longestConsecutive(TreeNode* root) {
if (!root) return 0;
int res = 0;
dfs(root, root->val - 1, 0, res);
return res;
}
void dfs(TreeNode *root, int v, int out, int &res) {
if (!root) return;
if (root->val == v + 1) ++out;
else out = 1;
res = max(res, out);
dfs(root->left, root->val, out, res);
dfs(root->right, root->val, out, res);
}
};
分析
這道題讓我們求二叉樹的最長(zhǎng)連續(xù)序列靶壮，關(guān)于二叉樹的題基本都需要遍歷樹叠萍，而遞歸遍歷寫起來(lái)特別簡(jiǎn)單，上面這種解法是用到了遞歸版的先序遍歷，我們對(duì)于每個(gè)遍歷到的節(jié)點(diǎn)茸习，我們看節(jié)點(diǎn)值是否比參數(shù)值(父節(jié)點(diǎn)值)大1，如果是則長(zhǎng)度加1纬霞，否則長(zhǎng)度重置為1冻辩，然后更新結(jié)果res，再遞歸調(diào)用左右子節(jié)點(diǎn)即可触幼。
