Morris pre-order traversal in Java, O(1) space


  • 1
    H

    Very similar to in-order traversal.

    public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        TreeNode curr = root, prev = null;
        while(curr!=null){
            if(curr.left==null){
                result.add(curr.val);
                curr = curr.right;
            }else{
                prev = curr.left;
                while(prev.right!=null && prev.right!= curr)
                    prev = prev.right;
                if(prev.right == null){
                    prev.right = curr;
                    result.add(curr.val);
                    curr = curr.left;
                }else{
                    prev.right = null;
                    curr = curr.right;
                }
            }
        }
        return result;
    }
    

    }


Log in to reply
 

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