Postorder Traversal

后序遍历有三种，一种是双栈辅助完成迭代，一种是单栈辅助，还有一种是Morris Traversal

• Two stacks

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []

        a, b = [root], []
        res = []

        while a:
            node = a.pop()
            b.append(node)
            if node.left:
                a.append(node.left)
            if node.right:
                a.append(node.right)

        while b:
            res.append(b.pop().val)

        return res

Java版本

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

       Stack<TreeNode> a = new Stack<TreeNode>();
       Stack<TreeNode> b = new Stack<TreeNode>();
       List<Integer> result = new ArrayList<>();
       a.add(root);

       while (!a.isEmpty()) {
           TreeNode node = a.pop();
           b.add(node);
           if (node.left != null) {
               a.add(node.left);
           }
           if (node.right != null) {
               a.add(node.right);
           }
       }

       while (!b.isEmpty()) {
           result.add(b.pop().val);
       }

       return result;
    }
}

• One stack

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []

        stack, h, c = [root], root, None
        res = []

        while stack:
            c = stack[-1]
            if c.left and c.left != h and c.right != h:
                stack.append(c.left)
            elif c.right and c.right != h:
                stack.append(c.right)
            else:
                h = c
                res.append(stack.pop().val)

        return res

• Morris Traversal

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        pre, cur = root, None
        res = []

        while pre:
            cur = pre.left
            if cur:
                while cur.right and cur.right != pre:
                    cur = cur.right
                if not cur.right:
                    cur.right = pre
                    pre = pre.left
                    continue
                else:
                    cur.right = None
                    self.pe(pre.left, res)
            pre = pre.right
        self.pe(root, res)

        return res

    def pe(self, root, lst):
        tail = self.reverse(root)
        cur = tail
        while cur:
            lst.append(cur.val)
            cur = cur.right
        self.reverse(tail)

    def reverse(self, root):
        pre, nxt = None, None
        while root:
            nxt = root.right
            root.right = pre
            pre = root
            root = nxt
        return pre