0145. Binary Tree Postorder Traversal.md

• 145 . Binary Tree Postorder Traversal
• 难度：Easy｜ 简单
• 相关知识点：Binary Tree
• 题目链接：https://leetcode.com/problems/binary-tree-postorder-traversal/description/

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

Example 1:


Input: root = [1,null,2,3]
Output: [3,2,1]
Example 2:

Input: root = []
Output: []
Example 3:

Input: root = [1]
Output: [1]
 

Constraints:

The number of the nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?

Solution1 : recursion

# 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: Optional[TreeNode]) -> List[int]:
        ret = []
        if root:
            ret.extend(self.postorderTraversal(root.left))
            ret.extend(self.postorderTraversal(root.right))
            ret.append(root.val)
        return ret

Solution2 : non-recursion

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ret = []
        stack = []
        r = root
        while stack or r:
            if r:
                stack.append(r)
                ret.append(r.val)
                r = r.right
            else:
                r = stack.pop()
                r = r.left
        return ret[::-1]

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ret = []
        stack = []
        if root:
            stack.append(root) 
        while stack:
            r = stack.pop()
            ret.append(r.val)
            if r.left:
                stack.append(r.left)
            if r.right:
                stack.append(r.right) 
        return ret[::-1]

use queue

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        node = root
        l = deque()
        dq = deque()
        while node or stack:
            if node:
                stack.append(node)
                l.appendleft(node.val)
                node = node.right
            else:
                node = stack.pop()
                node = node.left
        return l