It looks fine but I do not understand why time limit is exceeded.


  • 0
    S

    Hi,

    My approach is to make another function, loop, that flattens the tree but also connects the head and the tail of the flattened list. And make another function to connect two loops, (root + left) + right.

    public class Solution {
        void bridge(TreeNode node1, TreeNode node2)   {
            if (node1 != null)
                node1.right = node2;
                
            if (node2 != null)
                node2.left = node1;
        }
        
        void connect(TreeNode loop1, TreeNode loop2)    {
            if (loop1 == null || loop2 == null)
                return;
            
            // bridge loop1 <-> loop2
            TreeNode last = loop2.left;
            bridge(loop1.left, loop2);
    
            // bridge <- loop1, loop2 ->
            bridge(last, loop1);
        }
        
        void loop(TreeNode root) {
        	if (root == null)
        		return;
            // flatten the root, but wire the first and the last in the cirular way.
        	TreeNode left = root.left;
        	TreeNode right = root.right;
            loop(left);
            loop(right);
            bridge(root, root);
            
            connect(root, left);
            connect(root, right);
        }
    
        public void flatten(TreeNode root) {
            if (root == null)
                return;
                
            loop(root);
            bridge(root.left, null);
            bridge(null, root);
        }
    }

Log in to reply
 

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