leetcode145 -- Binary Tree Postorder Traversal (二叉树后根序遍历)

# 小郑之家~

### 题目

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [3,2,1]


### 递归


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

class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:

res = []
if not root:
return []
self.postorder(root, res)
return res

def postorder(self, root, res):
if not root:
return

self.postorder(root.left, res)
self.postorder(root.right, res)
res.append(root.val)


### 非递归的话


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

class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:

res = []
stack = []
p = root
while len(stack)>0 or p:
if p:
stack.append(p)
res.insert(0, p.val)
p = p.right
else:
t = stack.pop()
p = t.left

return res