145 Binary Tree Postorder Traversal

145. Binary Tree Postorder Traversal

1. Question

Given a binary tree, return the postorder traversal of its nodes' values.

For example: Given binary tree{1,#,2,3},

   1
    \
     2
    /
   3

return[3,2,1].

2. Implementation

(1) Morris Tree Traversal

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        TreeNode dummy = new TreeNode(0);
        dummy.left = root;
        TreeNode curNode = dummy, preNode = null;

        while (curNode != null) {
            if (curNode.left == null) {
                curNode = curNode.right;
            }
            else {
                preNode = curNode.left;
                while (preNode.right != null && preNode.right != curNode) {
                    preNode = preNode.right;
                }
                // Traversing down to the left
                if (preNode.right == null) {
                    preNode.right = curNode;
                    curNode = curNode.left;
                }
                // Traversing up from the right
                else {
                    TreeNode node = preNode;
                    reverse(curNode.left, preNode);
                    while (node != curNode.left) {
                        res.add(node.val);
                        node = node.right;
                    }
                    res.add(node.val);
                    reverse(preNode, curNode.left);
                    preNode.right = null;
                    curNode = curNode.right;
                }
            }
        }
        return res;
    }

    public void reverse(TreeNode from, TreeNode to) {
        if (from == to) {
            return;
        }

        TreeNode preNode = from, curNode = from.right, nextNode = null;
        while (preNode != to) {
            nextNode = curNode.right;
            curNode.right = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
    }
}

(2) Iteration

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode curNode = null, preNode = null;

        while (!stack.isEmpty()) {
            curNode = stack.peek();
            // Case 1: Traverse down the tree, put left child into stack if it exists, otherwise put right child
            if (preNode == null || preNode.left == curNode || preNode.right == curNode) {
                if (curNode.left != null) {
                    stack.push(curNode.left);
                }
                else if (curNode.right != null) {
                    stack.push(curNode.right);
                }
            }
            // Case 2: Travese up from left child
            else if (curNode.left == preNode) {
                if (curNode.right != null) {
                    stack.push(curNode.right);
                }
            }
            // Case 3: Traverse up from right child
            else {
                res.add(curNode.val);
                stack.pop();
            }
            preNode = curNode;
        }
        return res;
    }
}

3. Time & Space Complexity

(1) Morris Tree Traversal: 时间复杂度: O(n), 空间复杂度: O(1)

(2) Iteration: 时间复杂度: O(n), 空间复杂度: O(h)