[数据结构与算法]【Python】【LeetCode.145】二叉树的后序遍历

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
1

2
/
3

输出: [3,2,1]

首先当然是喜闻乐见的递归

# class TreeNode:
	# def __init__(self, val=0, left=None, right=None):
		# self.val = val
		# self.left = left
		# self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
    	if not root:
    		return []
    	return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

显然，用递归就有点耍流氓了。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
    	res = []
    	stack = []
    	cur = root
    	while stack or cur:
    		while cur: # 后序：左-右-根，这里先反过来：根-右-左
    			res.append(cur.val)
    			stack.append(cur)
    			cur = cur.right
    		cur = stack.pop()
    		cur = cur.left
    	return res[::-1] # 将根-右-左倒序，得到后序：左-右-根