Binary Tree Longest Consecutive Sequence II

题目

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input:

        1
       / \
      2   3

Output:
 2

Explanation:
 The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input:

        2
       / \
      1   3

Output:
 3

Explanation:
 The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Note:All the values of tree nodes are in the range of [-1e7, 1e7].

思路分析

这道题是Binary Tree Longest Consecutive Sequence的延伸，主要的思想是一样的，就是用DFS来实现，下面的注释的code就是被优化的地方

//Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        int[] result = new int[1];
        dfs(root, result);
        return result[0];
    }
    public int[] dfs(TreeNode root, int[] result){
        if (root == null) return new int[]{0, 0};
        int[] left = dfs(root.left, result);
        int[] right= dfs(root.right, result);
        int increaseLcs=1, decreaseLcs=1;

        if(root.left!=null && root.val+1 == root.left.val) left[0]++;
        else left[0] = 1;
        if(root.right!=null && root.val+1 == root.right.val) right[0]++;
        else right[0] = 1;
        if(root.left!=null && root.val-1 == root.left.val) left[1]++;
        else left[1] = 1;
        if(root.right!=null && root.val-1 == root.right.val) right[1]++;
        else right[1] = 1;

        increaseLcs = left[0] > right[0]? left[0] : right[0];
        decreaseLcs = left[1] > right[1]? left[1] : right[1];
        /*
        int max1 = 0, max2 = 0;
        if (root.left!=null && root.val+1 == root.left.val && root.right!=null && root.val-1 == root.right.val) {
            max1 = left[0] + right[1] - 1;
        }
        if (root.left!=null && root.val-1 == root.left.val && root.right!=null && root.val+1 == root.right.val) {
            max2 = left[1] + right[0] - 1;
        }
        int max3 = Math.max(Math.max(max1, max2), Math.max(increaseLcs, decreaseLcs));
        */  <<<<< 这一段被注释掉的代码可以被increaseLcs+decreaseLcs-1所代替
        result[0] = Math.max(result[0], increaseLcs+decreaseLcs-1);
        return new int[]{increaseLcs, decreaseLcs};
    }
}