Java recursively compute ascending and descending sequence


  • 8

    For each subtree we recursively compute the length of longest ascending and descending path starting from the subtree root. Then we can efficiently check if we could join the two subtree together to get a longer child-parent-child path. In another word, for each subtree, the longest child-parent-child consecutive (with root being the parent) is dec+inc-1 since both the ascending and descending path start from root.

        private int maxlen = 0;
        private int[] helper(TreeNode root) {
            if (root == null) return new int[]{0, 0};
            int inc = 1, dec = 1;
            int[] left = helper(root.left), right = helper(root.right);
            if (root.left != null) {
                if (root.left.val == root.val+1) inc += left[0];
                if (root.left.val == root.val-1) dec += left[1];
            }
            if (root.right != null) {
                if (root.right.val == root.val+1) inc = Math.max(inc, 1+right[0]);
                if (root.right.val == root.val-1) dec = Math.max(dec, 1+right[1]);
            }
            maxlen = Math.max(inc+dec-1, maxlen);
            return new int[]{inc, dec};
        }
        public int longestConsecutive(TreeNode root) {
            helper(root);
            return maxlen;
        }
    

  • 0
    Y

    @dreamchase Very nice solution!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.