postOrder Traversal

题目描述

解题方法

• 递归
• iterative, stack
• morris方法

stack

postorder比inorder, preorder复杂一些

Solution

递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

    def helper(self, result, root):
        if not root:
            return

        self.helper(result, root.left)
        self.helper(result, root.right)
        result.append(root.val)

iterative stack

• 用一个cur来track当前到达的点（不是postorder result的顺序，而是当前visit的）
• 用一个pre来track之前遍历的那个点（postorder中的，所以只在加到result数组的时候更新），对每一个root,依然是不断将left加到stack上到底
• 当None的时候，是否要往右边走需要判断是否已经visit过right,所以Pre在这里就有了用处

具体步骤是

1. 一开始也是不断地将left child放到stack上,用cur记录当前的node,用pre来记录上一个node（这时候不加到result数组）
2. 当cur为None时，有几种情况
   • 如果当前stack顶元素tmp的右节点存在，并且没有访问过(prev != tmp.right)，就应该往tmp的右边走
   • 否则的话，说明右节点是空的，或者右节点已经访问过了，那么就可以将当前的pop出来加到result里了，这个时候再更新prev

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        result = []
        stack = []
        pre = None
        cur = root
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                tmp = stack[-1] #need to compare with pre, so don't pop now
                if tmp.right and pre != tmp.right:
                    #right exists and is unvisited, so go right
                    cur = tmp.right
                else:
                    top = stack.pop()
                    result.append(top.val)
                    pre = top

        return result

Morris

Reference