Java AC iterative without lifo - Morris preorder


  • 0
    I

    It's really simple. Almost the same code can be used for inorder and preorder traversal. Before travelling down left, we modify the most right leaf in the left child that will be the last node visited in the left branch to point to the current node so we could visit current right branch later. When we come back to the same point using our modification, we just do the same thing again but now we will detect previously created modification/cycle and remove it. At the end tree stays untouched. It's based on threaded trees. wiki: threaded binary tree

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

Log in to reply
 

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