代码随想训练营的第十五天（Python）｜ 二叉树的前、中、后续遍历（各种花式遍历哈哈）

前序遍历
统一写法用None 来区分遍历查找的节点和处理节点
1、递归法

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        self.preorder(root, res)
        return res

    def preorder(self, root, res):
        if root is None:
            return
        res.append(root.val) # 中
        self.preorder(root.left, res) # 左
        self.preorder(root.right, res)  # 右

2、迭代法

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            if not node:
                return res
            res.append(node.val) # 中
            if node.right:
                stack.append(node.right) # 右
            if node.left:
                stack.append(node.left) # 左
        return res

3、统一写法

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            # 查找节点处理
            if node:
                # 右
                if node.right:
                    st.append(node.right)
                # 左
                if node.left:
                    st.append(node.left)
                # 中
                st.append(node)
                st.append(None)
            else:
                node = st.pop()
                res.append(node.val)
        return res

中序遍历
1、递归法

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        self.inorder(root, res)
        return res

    def inorder(self, root, res):
        if root is None:
            return
        self.inorder(root.left, res) # 左
        res.append(root.val)     # 中
        self.inorder(root.right, res) # 右

2、迭代法

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = []
        cur = root # 指针
        while cur or stack:
            # 左
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop() # 中
                res.append(cur.val)
                cur = cur.right   # 右
        return res

3、统一写法

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            # 查看节点
            if node:
                # 右
                if node.right:
                    st.append(node.right)
                # 中
                st.append(node)
                st.append(None)
                #左
                if node.left:
                    st.append(node.left)
            # 处理节点
            else:
                node = st.pop()
                res.append(node.val)
        return res

后续遍历
1、递归法

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        self.postorder(root, res)
        return res

    def postorder(self, root, res):
        if root is None:
            return
        self.postorder(root.left, res) # 左
        self.postorder(root.right, res) # 右
        res.append(root.val) # 中

2、迭代法1

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = [root]
        while stack:
            # 中
            node = stack.pop()
            if node is None:
                return res
            res.append(node.val)

            # 左
            if node.left:
                stack.append(node.left)

            # 右
            if node.right:
                stack.append(node.right)

        # 结果为中右左 反转后是 左右中
        return res[::-1]

3、迭代法2

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = []
        pre, cur = None, root # pre 记录已经遍历过的右子节点
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                # 没有右子节点或者右子节点已经遍历过可以将这个节点加入到结果集
                if not cur.right or pre == cur.right:
                    res.append(cur.val)
                    pre = cur
                    cur = None
                else:
                    # 这个节点有节点需要再次入栈
                    stack.append(cur)
                    cur = cur.right
        return res

4、统一写法

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            # 查找节点
            if node:
                # 中
                st.append(node)
                st.append(None) # 作标记

                # 右
                if node.right:
                    st.append(node.right)

                # 左
                if node.left:
                    st.append(node.left)
            # 处理节点
            else:
                node = st.pop()
                res.append(node.val)
        return res