Morris traversal can be applied, solution in Java


  • 0
    X

    If you know Morris traversal, it requires no extra space, so it's more space efficient than recursion or iterative solution. It's vary easy when we apply it for inorder and preorder, but for preorder it's a little bit hard.

    We need a dummy node and a reverse function to implement the algorithm.

    List<Integer> rst = new ArrayList<Integer>();
    
    private void reverse(TreeNode start, TreeNode end) {
    	TreeNode run = start.right;
    	while (start != end) {
    		TreeNode temp = run.right;
    		run.right = start;
    		start = run;
    		run = temp;
    	}
    }
    
    private void printReverse(TreeNode start, TreeNode end) {
    	reverse(start, end);
    	TreeNode run = end;
    	while (run != start) {
    		rst.add(run.val);
    		run = run.right;
    	}
    	rst.add(run.val);
    	reverse(end, start);
    }
    
    public List<Integer> postorderTraversal(TreeNode root) {
        TreeNode dummy = new TreeNode(0);
    	dummy.left = root;
    	root = dummy;
    	while (root != null) {
    		if (root.left == null) 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;
    				root = root.left;
    			} else {
    				run.right = null;
    				printReverse(root.left, run);
    				root = root.right;
    			}
    		}
    	}
    	return rst;
    }

Log in to reply
 

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