Morris Traversal, O(n) time, O(1) space, can be applied to inorder and postorder


  • 2
    X
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> rst = new ArrayList<Integer>();
        while (root != null) {
    		if (root.left == null) {
    			rst.add(root.val);
    			root = root.right;
    		} else {
    			TreeNode run = root.left;
    			while (run.right != null && run.right != root) run = run.right;
    			if (run.right == null) {
    				run.right = root;
    				rst.add(root.val);
    				root = root.left;
    			} else {
    				run.right = null;
    				root = root.right;
    			}
    		}
    	}
    	return rst;
    }

  • 0
    F

    Nice solution! I applied your idea to post-order traversal


  • 0
    N

    @flacosun Hey! Spoiler Alert!


Log in to reply
 

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