【LeetCode - 549】二叉树中最长的连续序列

1、题目描述

2、解题思路

  给每一个节点搭配两个属性：inc 和 dcr 。

  其中，inc 表示截至到当前节点的最长连续递增序列的长度，dcr 表示截至到当前节点的最长连续递减序列的长度。

  那么，包含当前节点的连续序列路径的长度就是 inc + dec - 1。

  接着找到 inc + dec - 1 值最大的节点，返回这个值即可。

3、解题代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {int maxval = 0;public int longestConsecutive(TreeNode root) {longestPath(root);return maxval;}public int[] longestPath(TreeNode root) {if (root == null) {return new int[]{0, 0};}int inr = 1, dcr = 1;if (root.left != null) {int[] l = longestPath(root.left);if (root.val == root.left.val + 1) {dcr = l[1] + 1;} else if (root.val == root.left.val - 1) {inr = l[0] + 1;}}if (root.right != null) {int[] r = longestPath(root.right);if (root.val == root.right.val + 1) {dcr = Math.max(dcr, r[1] + 1);} else if (root.val == root.right.val - 1) {inr = Math.max(inr, r[0] + 1);}}maxval = Math.max(maxval, dcr + inr - 1);return new int[]{inr, dcr};}
}