python实现-二叉树的前序，中序，后序遍历

利用递归

前序遍历

# 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 preorderTraversal(self, root: TreeNode) -> List[int]:
        ans = list()
        def preorder(node):
            if not node:
                return
            ans.append(node.val)
            preorder(node.left)
            preorder(node.right)
        preorder(root)
        return ans

中序遍历

# 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 inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = list()
        def inorder(node):
            if not node:
                return 
            inorder(node.left)
            ans.append(node.val)
            inorder(node.right)
        
        inorder(root)
        return ans

后序遍历

# 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]:
        
        ans = list()

        def postorder(node):
            if not node:
                return 
            postorder(node.left)
            postorder(node.right)
            ans.append(node.val)
        
        postorder(root)
        return ans

迭代的模式

前序遍历

# 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 preorderTraversal(self, root: TreeNode) -> List[int]:
        ans = list()

        stack = list()

        while stack or root:
            while root:
                # 前序遍历，先添加一个
                ans.append(root.val)
                # 将左边的节点压入栈中
                stack.append(root)
                root = root.left
            # 从栈中弹出最后一个node
            root = stack.pop()
            # 去看这个node的右节点
            root = root.right
        
        return ans