Given a binary tree, return the postorder traversal of its nodes’ values.
(后序遍历二叉树)
Follow up: Recursive solution is trivial, could you do it iteratively?
Example:
1. 递归
具体实现方法如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
class (object): def helper(self, root, res): if not root: return res self.helper(root.left, res) self.helper(root.right, res) res.append(root.val) def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return []
result = [] self.helper(root, result) return result
|
2. 迭代 & 栈
由于先序遍历的顺序是根-左-右,后序遍历的顺序是左-右-根,因此可以修改先序遍历的遍历顺序为根-右-左,然后将最终结果倒序即可。具体实现方法如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
class (object): def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return [] result, stack = [], [] p = root while stack or p: if p: result.append(p.val) stack.append(p.left) p = p.right else: p = stack.pop() return result[::-1]
|
近期评论