Post Order Travel O(n) time


  • 0
    V

    The logic is to boil up a "packet" from child nodes to the parent node. This packet contains max consecutive length thus far. So, compare the packet coming from the left child and the packet from the right child, pick the best one and compare it with the parent.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        class Packet {
            TreeNode node;
            int length;
            
            Packet(TreeNode n, int len)
            {
                node = n;
                length = len;
            }
        }
        
        Packet solutionPacket = null;
        public int longestConsecutive(TreeNode root) {
           Packet tempSol = Utility(root);
           if(solutionPacket == null || tempSol.length > solutionPacket.length)
           {
               solutionPacket = tempSol;
           }
           
           if(solutionPacket == null)
           {
               return 0;
           }
           
           if(solutionPacket.node == null)
           {
               return 0;
           }
           
           return solutionPacket.length;
        }
        
        public Packet Utility(TreeNode root)
        {
            if(root == null)
            {
                return new Packet(null, 0);
            }
            
            Packet left = Utility(root.left);
            Packet right = Utility(root.right);
            Packet p = left;
            if(left.length == 0 &&  right.length == 0)
            {
                p = left;
            }
            else 
            if(left.length != 0 && right.length != 0 && left.length == right.length)
            {
                if(left.node.val - 1 == root.val)
                {
                    p = left;
                }
                else
                {
                    if(right.node.val - 1 == root.val)
                    {
                        p = right;
                    }
                }
            }
            else
            {
                if(left.length > right.length)
                {
                    p = left;
                }
                else
                {
                    p = right;
                }
            }
            
            
            if(solutionPacket == null || p.length > solutionPacket.length)
            {
                solutionPacket = p;
            }
            
            if(p.node != null)
            {
                if(p.node.val - 1 == root.val)
                {
                    return new Packet(root, p.length+1);
                }
                else
                {
                   return new Packet(root, 1); 
                }
            }
            return new Packet(root, 1);
        }
    }
    

Log in to reply
 

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