Idea similar to finding paths that sum up to a given value.


  • 0

    We need to consider 6 cases.

    1. Root + left subtree forms an increasing sequence if root + 1 == node.left.
    2. Root + left subtree forms a decreasing sequence if root -1 == node.left.
      3 & 4 are similar cases for the right subtree.
    3. if the root + 1 == node.left and root -1 == node.right, we need to club the increasing sequence from left sub-tree and the decreasing sequence from right sub-tree to form an increasing V-path.
    4. if the root - 1 == node.left and root + 1 == node.right, we need to club the decreasing sequence from left sub-tree and the increasing sequence from right sub-tree to form a decreasing V path.

    The longest increasing and decreasing subtree starting at root need to be returned.

    public class Solution {
        private int maxPath = 0;
        public int LongestConsecutive(TreeNode root)
        {
            GetLongestConsecutive(root);
            return maxPath;
        }
    
        public int[] GetLongestConsecutive(TreeNode root)
        {
            if (root == null)
            {
                return null;
            }
    
            int[] curSequence = new int[] { 1, 1 }, rightSequences = null, leftSequences = null;
    
            if (root.left != null)
            {
                leftSequences = GetLongestConsecutive(root.left);
                if (root.val + 1 == root.left.val)
                {
                    // Increasing sequence
                    curSequence[0] = leftSequences[0] + 1;
                }
    
                if (root.val - 1 == root.left.val)
                {
                    // Decreasing sequence
                    curSequence[1] = leftSequences[1] + 1;
                }
            }
    
            if (root.right != null)
            {
                rightSequences = GetLongestConsecutive(root.right);
                if (root.val + 1 == root.right.val)
                {
                    // Increasing sequence
                    curSequence[0] = Math.Max(curSequence[0], rightSequences[0] + 1);
                }
    
                if (root.val - 1 == root.right.val)
                {
                    // Decreasing sequence
                    curSequence[1] = Math.Max(curSequence[1], rightSequences[1] + 1);
                }
            }
    
            maxPath = Math.Max(maxPath, Math.Max(curSequence[0], curSequence[1]));
            if (root.left != null && root.right != null)
            {
                if (root.left.val - 1 == root.val && root.val == root.right.val + 1)
                {
                    // Increasing v sequence.
                    maxPath = Math.Max(maxPath, leftSequences[0] + rightSequences[1] + 1);
                }
    
                if (root.left.val + 1 == root.val && root.val == root.right.val - 1)
                {
                    // Decreasing v sequence.
                    maxPath = Math.Max(maxPath, leftSequences[1] + rightSequences[0] + 1);
                }
            }
    
            return curSequence;
        }
    }
    

Log in to reply
 

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