Binary Tree Longest Consecutive Sequence: Post-Order Traversal

-
Problem is here: https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
298. Binary Tree Longest Consecutive Sequence
Medium
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).
Example 1:
Input:

   1
    \
     3
    / \
   2   4
        \
         5

Output: 3

Explanation: Longest consecutive sequence path is 3-4-5, so return 3.
Example 2:
Input:

   2
    \
     3
    / 
   2    
  / 
 1

Output: 2 

Explanation: Longest consecutive sequence path is 2-3, not 3-2-1, so return 2.
Best option is to perform a post-order tree traversal:

  • Call for the left node
  • Call for the right node
  • Then calculate the value of the current node by checking whether the left AND the right are potential candidates for a sequence
Because the sequence has to be in increasing order, it limits the different conditions to check for. Still, there are some variations that need to be addressed, like when only one node exists, both exist, when only one node match the increasing condition, when both match, and so on. Code is down below, cheers, ACC.


public class Solution
{
    public int LongestConsecutive(TreeNode root)
    {
        int longestEndingHere = 0;
        int longest = 0;
        LongestConsecutive(root, ref longestEndingHere, ref longest);
        return longest;
    }

    private void LongestConsecutive(TreeNode node,
                                    ref int longestEndingHere,
                                    ref int longest)
    {
        if (node == null) return;

        int leftLongestEndingHere = 0;
        LongestConsecutive(node.left, ref leftLongestEndingHere, ref longest);
        int rightLongestEndingHere = 0;
        LongestConsecutive(node.right, ref rightLongestEndingHere, ref longest);

        longestEndingHere = 1;
        if (node.left == null && node.right == null)
        {
            //No-op
        }
        else if (node.left == null)
        {
            if (node.val + 1 == node.right.val)
            {
                longestEndingHere += rightLongestEndingHere;
            }
        }
        else if (node.right == null)
        {
            if (node.val + 1 == node.left.val)
            {
                longestEndingHere += leftLongestEndingHere;
            }
        }
        else
        {
            if (node.val + 1 == node.right.val && node.val + 1 == node.left.val)
            {
                longestEndingHere += Math.Max(leftLongestEndingHere, rightLongestEndingHere);
            }
            else if (node.val + 1 == node.right.val)
            {
                longestEndingHere += rightLongestEndingHere;
            }
            else if (node.val + 1 == node.left.val)
            {
                longestEndingHere += leftLongestEndingHere;
            }
        }

        longest = Math.Max(longest, longestEndingHere);
    }
}

Comments

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more