遞歸遍歷 （必須掌握）:

前序遍歷：中左右

# 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 = []
        def travelsal(root:TreeNode):
            if root == None:
                return 
            res.append(root.val)
            travelsal(root.left)
            travelsal(root.right)
        travelsal(root)
        return res 

中序遍歷：左中右

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def travelsal(root):
            if root == None:
                return 
            travelsal(root.left)
            res.append(root.val)
            travelsal(root.right)
        travelsal(root)
        return res

后續(xù)遍歷：左右中

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def traversal(root):
            if root == None:
                return
            traversal(root.left)
            traversal(root.right)
            res.append(root.val)
        traversal(root)
        return res

遞歸遍歷二叉樹模板：

def  f1(root:TreeNode):
  res =[]
  def f2(root):
      if root == None:
          return 
     f2(root.left) #左
     f2(root.rigth) #右
     res.append(root.val) #中
 f2(root)
return res 

調(diào)整f2中左右中的位置實現(xiàn)三種不同的遍歷

迭代遍歷：

前序遍歷

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st= []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right: #右
                    st.append(node.right)
                if node.left: #左
                    st.append(node.left)
                st.append(node) #中
                st.append(None)
            else:
                node = st.pop()
                result.append(node.val)
        return result

中序遍歷

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st= []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right: #右
                    st.append(node.right)
                st.append(node) #中
                st.append(None)
                if node.left: #左
                    st.append(node.left)
            else:
                node = st.pop()
                result.append(node.val)
        return result

后序遍歷

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st= []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                st.append(node) #中
                st.append(None)
                if node.right: #右
                    st.append(node.right)
                if node.left: #左
                    st.append(node.left)
            else:
                node = st.pop()
                result.append(node.val)
        return result

迭代遍歷統(tǒng)一模板：

def  Travelsal(root):
      res = []
     st = []
     if root:
         st.append(root)
     while st:
         node = st.pop()
         if node != None:
             #左右中按照輸出順序的反順序?qū)?        else:
           node = st.pop()
           res.append(node.val)
     return res