[数据结构与算法]迭代遍历二叉树

需要画图理解，递归是好写，但是性能垃圾

前序遍历

思路：用栈实现，先处理当前节点，右孩子先入栈，左孩子后入栈。

# 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: Optional[TreeNode]) -> List[int]:
        res = []
        
        if not root:
            return res

        stack = [root]
        
        while stack:
            node = stack.pop() # 先处理中间节点
            res.append(node.val)
            
            # 然后右孩子入栈，左孩子入栈
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
            
        return res

中序遍历

中序遍历不能和前序遍历一样，因为res存储的元素和访问的元素的顺序并非一致
中序遍历：左中右
前序遍历：中左右

# 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: Optional[TreeNode]) -> List[int]:
        res = []
        if not root:
            return res
        
        stack = [] # 不能把node提前放进栈
        cur = root
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                node = stack.pop() # 中间节点
                res.append(node.val)
                
                cur = node.right
        return res

后序遍历

前序遍历是 中左右 左孩子先入栈 中右左 将结果翻转 得到左右中
后序遍历是 左右中

# 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]:
        res = []
        if not root:
            return res
        
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            
            # 左孩子先入栈
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
            
        return res[::-1]