145. Binary Tree Postorder Traversal
题目:
https://leetcode.com/problems/binary-tree-postorder-traversal/
难度:
Hard
wikipedia 助你幸福
递归版本
postorder(node)
if (node = null)
return
postorder(node.left)
postorder(node.right)
visit(node)
迭代版本
iterativePostorder(node)
s ← empty stack
lastNodeVisited ← null
while (not s.isEmpty() or node ≠ null)
if (node ≠ null)
s.push(node)
node ← node.left
else
peekNode ← s.peek()
// if right child exists and traversing node
// from left child, then move right
if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
node ← peekNode.right
else
visit(peekNode)
lastNodeVisited ← s.pop()
刷进度直接用递归AC
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
self.result = []
self.postOrder(root)
return self.result
def postOrder(self, root):
if root == None : return
self.postOrder(root.left)
self.postOrder(root.right)
self.result.append(root.val)
