二叉树的后序遍历☆☆☆

递归

# 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]:
        if root is None: return []
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [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]:
        # 左 - 右 - 根
        if not root: return []
        stack = []
        mark_node = None
        ans = []
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            elif stack[-1].right != mark_node:
                root = stack[-1].right
                mark_node = None
            else:
                mark_node = stack.pop()
                ans.append(mark_node.val)
        return ans

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if root==None:
            return []
        stack=[root]
        res=[]
        while stack:
            s=stack.pop()
            res.append(s.val)
            if s.left:#与前序遍历相反
                stack.append(s.left)
            if s.right:
                stack.append(s.right)
        return res[::-1]
作者：harris-han
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/python3-er-cha-shu-hou-xu-bian-li-die-dai-fang-fa-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 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 = []  
        node = root
        while stack or node:
            while node:
                stack.append(node)  # 第一次入栈的是根节点
                #判断当前节点的左子树是否存在，若存在则持续左下行，若不存在就转向右子树
                node = node.left if node.left is not None else node.right
            #循环结束说明走到了叶子节点，没有左右子树了，该叶子节点即为当前栈顶元素，应该访问了
            node = stack.pop() # 取出栈顶元素进行访问
            res.append(node.val) # 将栈顶元素也即当前节点的值添加进res
            # （下面的stack[-1]是执行完上面那句取出栈顶元素后的栈顶元素）
            if stack and stack[-1].left == node: #若栈不为空且当前节点是栈顶元素的左节点
                node = stack[-1].right   ## 则转向遍历右节点
            else:
                node = None  # 没有左子树或右子树，强迫退栈
        return res
作者：da-da-meng-yang
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-die-dai-fa-by-da-da-m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 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]:
        # 左 - 右 - 根
        if not root: return []
        stack = []
        ans = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left if root.left is not None else root.right
            root = stack.pop()
            ans.append(root.val)
            if stack and stack[-1].left == root:
                # 栈不为空，且当前节点是栈顶元素的左节点
                # 遍历右节点
                root = stack[-1].right
            else:
                root = None # 左右节点都遍历完，强制出栈
        return ans