145. Binary Tree Postorder Traversal 二叉树的后序遍历
难度: 困难
刷题内容
原题连接
- https://leetcode.com/problems/binary-tree-postorder-traversal
内容描述
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解题方案
思路 1
递归，so easy
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
if not root:
return res
left = self.postorderTraversal(root.left)
right = self.postorderTraversal(root.right)
if left:
res.extend(left)
if right:
res.extend(right)
res.append(root.val)
return res
思路 2
也可以先写一下后序遍历的函数，然后一个一个贴上去
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
def postOrder(root):
if not root : return
postOrder(root.left)
postOrder(root.right)
res.append(root.val)
res = []
postOrder(root)
return res
思路 3
迭代, 其实思路就一句话，后序遍历是左右中，因为我们第一个放进去的肯定是中（即root），所以我们逆向思维考虑一下，我们按照中右左的顺序放进去，然后返回res[::-1]就行了。这其实跟leetcode第144题是一样的思路
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
if not root:
return res
stack1 = []
stack1.append(root)
while len(stack1) > 0:
node = stack1.pop()
res.append(node.val)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
return res[::-1]
