Detail Explain about How Morris Traversal Finds two Incorrect Pointer


  • 108
    S

    To understand this, you need to first understand Morris Traversal or Morris Threading Traversal.
    It take use of leaf nodes' right/left pointer to achieve O(1) space Traversal on a Binary Tree.
    Below is a standard Inorder Morris Traversal, referred from http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html (a Chinese Blog, while the graphs are great for illustration)

    public void morrisTraversal(TreeNode root){
    		TreeNode temp = null;
    		while(root!=null){
    			if(root.left!=null){
    				// connect threading for root
    				temp = root.left;
    				while(temp.right!=null && temp.right != root)
    					temp = temp.right;
    				// the threading already exists
    				if(temp.right!=null){
    					temp.right = null;
    					System.out.println(root.val);
    					root = root.right;
    				}else{
    					// construct the threading
    					temp.right = root;
    					root = root.left;
    				}
    			}else{
    				System.out.println(root.val);
    				root = root.right;
    			}
    		}
    	}
    

    In the above code, System.out.println(root.val);appear twice, which functions as outputing the Node in ascending order (BST). Since these places are in order, replace them with

        if(pre!=null && pre.val > root.val){
        	if(first==null){first = pre;second = root;}
        	else{second = root;}
      }
    pre = root;
    

    each time, the pre node and root are in order as System.out.println(root.val); outputs them in order.

    Then, come to how to specify the first wrong node and second wrong node.

    When they are not consecutive, the first time we meet pre.val > root.val ensure us the first node is the pre node, since root should be traversal ahead of pre, pre should be at least at small as root. The second time we meet pre.val > root.val ensure us the second node is the root node, since we are now looking for a node to replace with out first node, which is found before.

    When they are consecutive, which means the case pre.val > cur.val will appear only once. We need to take case this case without destroy the previous analysis. So the first node will still be pre, and the second will be just set to root. Once we meet this case again, the first node will not be affected.

    Below is the updated version on Morris Traversal.

    public void recoverTree(TreeNode root) {
            TreeNode pre = null;
            TreeNode first = null, second = null;
            // Morris Traversal
            TreeNode temp = null;
    		while(root!=null){
    			if(root.left!=null){
    				// connect threading for root
    				temp = root.left;
    				while(temp.right!=null && temp.right != root)
    					temp = temp.right;
    				// the threading already exists
    				if(temp.right!=null){
    				    if(pre!=null && pre.val > root.val){
    				        if(first==null){first = pre;second = root;}
    				        else{second = root;}
    				    }
    				    pre = root;
    				    
    					temp.right = null;
    					root = root.right;
    				}else{
    					// construct the threading
    					temp.right = root;
    					root = root.left;
    				}
    			}else{
    				if(pre!=null && pre.val > root.val){
    				    if(first==null){first = pre;second = root;}
    				    else{second = root;}
    				}
    				pre = root;
    				root = root.right;
    			}
    		}
    		// swap two node values;
    		if(first!= null && second != null){
    		    int t = first.val;
    		    first.val = second.val;
    		    second.val = t;
    		}
        }

  • 2
    B

    This is great post, the explanation is both thoughtful and detailed. However, I think the algo would be much cleaner and neat if we wrap the "access root" part as a function. Thus in the two positions where we need to access the current root, we can call: accessNode (prev, root, first, second); which I think will increase the algo readability.


  • 3

    Great explanations, especially for the part discussing whether first and second is consecutive. In fact, the code can be further simplified. One obvious redundancy is

    if(first == null) {first = pre; second = root;}
    else {second = root;} 
    

    It is simply

    if(first==null) first = pre;
    second = root; 

  • 0
    J

    That part should handle the cases that first and second node is pre and root.


  • 0
    L

    @jianchao.li.fighter 's code can handle your case. If pre is null, then the next time, first will still be assigned.


  • -1
    H

    further optimization based on above sol.

    public class Solution {
      public void RecoverTree(TreeNode root) {
        TreeNode pre = null;
        TreeNode first = null;
        TreeNode second = null;
        while (root != null) {
          if (root.left != null) {
            var x = root.left;
            while (x.right != null && x.right != root) x = x.right;
            if (x.right == null) {
              x.right = root;
              root = root.left;
              continue;          
            } else x.right = null;
          }
          if (pre != null && root.val < pre.val) {
            if (first == null) first = pre;
            second = root;
          }
          pre = root;
          root = root.right;
        }  
        
    	var t = first.val;
    	first.val = second.val;
    	second.val = t;
      }
    }

  • 0
    U

    Can any one give me more detailed explanation about the part of "first = pre;second = root;"? I didn't understand why the first time we encounter "pre.val > root.val" ensures the incorrect node is the pre but not the root? Is it possible that it's actually the root is too small?


  • 0
    J

    @siyang3 well, the blog you posted is written in Chinese that I'm afraid that most people cannot read. Great explanation, though. Thank you.


  • 5

    @jtimberlakers
    I hope watch me please!!! can help you. It is quite intuitive. Thanks to the nice guy in the video.


  • 0
    N
    This post is deleted!

Log in to reply
 

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