Java Morris Traversal Solution got TLE? (tested fine on my PC so I don't understand..)


  • 0
    L

    Hello community,

    my code is based on morris traversal. In the first traversal it should generate the larger node of that swap (big). In the second traversal once it encounters a node with value bigger than that larger node, the previous encountered node should be the smaller one of that swap. Then I swap them back.

    I ran the code several times on my PC and no TLE at all, then I ran it on leetcode it got TLE so I really don't understand how come there can be a deadloop in the code...

    Thanks for all the help.

    Best,

    public void recoverTree(TreeNode root) {
        TreeNode node = root;
        TreeNode left = null;
        if (root==null){
        	return;
        }
        
        TreeNode pre = root;
        TreeNode cur = root;
        TreeNode big = root;
        
        while (node!=null){
        	if (node.left==null){
        		pre = cur;
        		cur = node;
        		if (pre.val>cur.val) {
        			big = pre;
        			break;
        		}
        		node = node.right;
        	} else {
        		left = node.left;
        		while (left.right!=null&&left.right.val!=node.val){
        			left = left.right;
        		}
        		if (left.right==null){
        			left.right = node;
        			node = node.left;
        		} else {
        			left.right = null;
        			pre = cur;
            		cur = node;
            		if (pre.val>cur.val) {
            			big = pre;
            			break;
            		}
        			node = node.right;
        		}
        	}	
        }
        while (node!=null){
        	if (node.left==null){
        		pre = cur;
        		cur = node;
        		if (cur.val>big.val) {
        			int tmp = big.val;
        			big.val = pre.val;
        			pre.val = tmp;
        			break;
        		}
        		node = node.right;
        	} else {
        		left = node.left;
        		while (left.right!=null&&left.right.val!=node.val){
        			left = left.right;
        		}
        		if (left.right==null){
        			left.right = node;
        			node = node.left;
        		} else {
        			left.right = null;
        			pre = cur;
            		cur = node;
            		if (cur.val>big.val) {
            			int tmp = big.val;
            			big.val = pre.val;
            			pre.val = tmp;
            			break;
            		}
        			node = node.right;
        		}
        	}	
        }
        
    }

  • 2
    Z

    I have got TLE too, finally I found the cause is that you shouldn't break or return during Morris Traversal。Here is my solution in Java for reference

    public void recoverTree(TreeNode root) {
    	TreeNode swapped = null, nextOfSwapped = null,prevNode = null;
    	// Morris Traversal
        while(root != null) {
        	if(root.left != null) {
        		TreeNode prev = findPrev(root);
        		if(prev.right == null) {
        			prev.right = root;
    
        			root = root.left;
        			continue;
        		} else {
        			prev.right = null;
        		}
        	}
        	// check if root is a swapped node
    		if(prevNode != null && prevNode.val > root.val) {
    			if(swapped == null) {
    				swapped = prevNode;
    				nextOfSwapped = root;
    			} else{ // found two swapped nodes
    				swap(swapped, root);
    				swapped = null;
    			}
    		}
    		prevNode = root;
        	root = root.right;
        }
    
        // found one swapped node
        if(swapped != null) {
        	swap(swapped, nextOfSwapped);
        }
    }
    
    private TreeNode findPrev(TreeNode node) {
    	TreeNode prev = node.left;
    	while(prev !=null && prev.right != null && prev.right != node) {
    		prev = prev.right;
    	}
    	return prev;
    }
    
    private void swap(TreeNode node1, TreeNode node2) {
    	int tmp = node1.val;
    	node1.val = node2.val;
    	node2.val = tmp;
    }

  • 0
    J

    I met the same problem but just don't understand why I cannot use the break statement?


  • 0
    A

    Because during the Morris Traversal you change the right child of each leave, you should finish the entire traversal to recover the leaves.


Log in to reply
 

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