Morris Traversal------- NO RECURSION NO STACK


  • 23
    B
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    
    public class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            if(root == null) return new ArrayList<Integer>();
            List<Integer> res = new ArrayList<Integer>();
            TreeNode pre = null;
            while(root != null){
            	if(root.left == null){
            		res.add(root.val);
            		root = root.right;
            	}else{
            		pre = root.left;
            		while(pre.right != null && pre.right != root){
            			pre = pre.right;
            		}
            		if(pre.right == null){
            			pre.right = root;
            			root = root.left;
            		}else{
            			pre.right = null;
            			res.add(root.val);
            			root = root.right;
            		}
            	}
            }
            return res;
        }
    }

  • 2

    Similar code. Morris traversal can do inorder and preorder. Postorder with Morris traversal is challenging. Google morris traversal for more info.

    Morris traversal can also be used to solve Recover binary search tree problem.

    Code:

    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> ret;
        if(!root) return ret;
        TreeNode* walker = root;
        while(walker) {
            if(walker->left) {
                TreeNode* walker2 = walker->left;
                while(walker2->right && walker2->right != walker) walker2 = walker2->right;
                if(!walker2->right) {
                    walker2->right = walker;
                    walker = walker->left;
                }
                else {
                    walker2->right = NULL;
                    ret.push_back(walker->val);
                    walker = walker->right;
                }
                continue;
            }
            ret.push_back(walker->val);
            walker = walker->right;
        }
        return ret;
    }
    

  • 0
    X

    You should add comments..


  • 0
    P

    More information can be found here https://codeoverflow.wordpress.com/tag/morris-inorder-traversal/. There are a couple of exmples to help figure it out.


Log in to reply
 

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