549. Binary Tree Longest Consecutive Sequence II

二刷 08/2022

Version #1 DFS

Time O(N)

Space O(N)

Runtime: 2 ms, faster than 50.69% of Java online submissions for Binary Tree Longest Consecutive Sequence II.

Memory Usage: 45.1 MB, less than 21.33% of Java online submissions for Binary Tree Longest Consecutive Sequence II.

class Solution {

    public int longestConsecutive(TreeNode root) {

        int[] max = new int[1];

        dfs(root, max);

        return max[0];

    }

    

    // returns the longest increasing/decreasing consecutive sequence

    private int[] dfs(TreeNode node, int[] max) {

        if (node == null) {

            return new int[]{0, 0};

        }

        int[] left = dfs(node.left, max);

        int[] right = dfs(node.right, max);

        int[] curr = new int[]{1, 1};

        if (node.left != null) {

            if (node.left.val == node.val - 1) {

                curr[0] = 1 + left[0];

            }

            if (node.left.val == node.val + 1) {

                curr[1] = 1 + left[1];

            }

        }

        if (node.right != null) {

            if (node.right.val == node.val - 1) {

                curr[0] = Math.max(curr[0], 1 + right[0]);

            }

            if (node.right.val == node.val + 1) {

                curr[1] = Math.max(curr[1], 1 + right[1]);

            }

        }

        max[0] = Math.max(max[0], curr[0] + curr[1] - 1);

        return curr;

    }

}

一刷

FLAW:
We don't have to distinguish the int leftAsc &rightAsc, leftDesc &rightDesc. Both of those pairs can be merged into maxAsc and maxDesc, and we can simply calculate the temp max path by maxAsc + 1 + maxDesc. In this way, the code will be neater.


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

class ResultType {
    public int maxAsc;
    public int maxDesc;
    public ResultType(int maxAsc, int maxDesc) {
        this.maxAsc = maxAsc;
        this.maxDesc = maxDesc;
    }
}

public class Solution {
    /**
     * @param root the root of binary tree
     * @return the length of the longest consecutive sequence path
     */
    int max = 0;
   
    public int longestConsecutive2(TreeNode root) {
        // Write your code here
     
        if (root == null) {
            return max;
        }
        helper(root);
        return max;
    }
 
    public ResultType helper(TreeNode root) {
        if (root == null) {
            return new ResultType(0, 0);
        }
     
        int maxAsc = 1;
        int maxDesc = 1;
     
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        //The root is not included
        int leftAsc = 0;
        int leftDesc = 0;
        int rightAsc = 0;
        int rightDesc = 0;
     
        if (root.left != null) {
            //descending up -> down
            if (root.val == root.left.val + 1) {
                leftDesc = left.maxDesc;
            } else if (root.val == root.left.val - 1) {
                //ascending up -> down
                leftAsc = left.maxAsc;
            }
        }
     
        if (root.right != null) {
            if (root.val == root.right.val + 1) {
                //descending up -> down
                rightDesc = right.maxDesc;
            } else if (root.val == root.right.val - 1) {
                //ascending up -> down
                rightAsc = right.maxAsc;
            }
        }
     
        int tempPath = Math.max(leftAsc + 1 + rightDesc, rightAsc + 1 + leftDesc);
        max = Math.max(max, tempPath);
     
        maxAsc = Math.max(maxAsc, leftAsc + 1);
        maxAsc = Math.max(maxAsc, rightAsc + 1);
        maxDesc = Math.max(maxDesc, leftDesc + 1);
        maxDesc = Math.max(maxDesc, rightDesc + 1);
     
        max = Math.max(max, maxAsc);
        max = Math.max(max, maxDesc);
        return new ResultType(maxAsc, maxDesc);
        //ResultType result = new ResultType();
     
    }
}