02 二叉樹6.翻轉二叉樹

方法1：迭代法，廣度優先遍歷（層序遍歷）

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        return root

方法2-1：遞歸法，前序遍歷

class Solution:
    def invertTree(self, root: TreeNode):
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

方法2-2：迭代法，前序遍歷

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        stack = [root]
        while stack:
            node = stack.pop()
            node.left, node.right = node.right, node.left
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return root

方法3-1：遞歸法：中序遍歷

這道題目使用前序遍歷和后序遍歷都可以，唯獨中序遍歷不方便，因為中序遍歷會把某些節點的左右孩子翻轉了兩次。

遞歸的中序遍歷是不行的，因為使用遞歸的中序遍歷，某些節點的左右孩子會翻轉兩次。

如果非要使用遞歸中序的方式寫，也可以，如下代碼就可以避免節點左右孩子翻轉兩次的情況：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def invertTree(self, root: TreeNode):
        if not root:
            return None
        self.invertTree(root.left)
        root.left, root.right = root.right, root.left
        self.invertTree(root.left) # 注意，這里處理的仍然是left
        return root

代碼雖然可以，但這畢竟不是真正的遞歸中序遍歷了。

但使用迭代方式統一寫法的中序是可以的。這是用棧來遍歷，而不是靠指針來遍歷，避免了遞歸法中翻轉了兩次的情況。

方法3-2：迭代法，偽中序遍歷（結果是對的，看起來像是中序遍歷，實際上它是前序遍歷，只不過把中間節點處理邏輯放到了中間。還是要用'統一寫法'才是真正的中序遍歷）：

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        stack = [root]
        while stack:
            node = stack.pop()
            if node.right:
                stack.append(node.right)
            node.left, node.right = node.right, node.left # 放到中間，依然是前序遍歷
            if node.right:
                stack.append(node.right) # 注意這里處理的仍然是right
        return root

方法3-3：迭代法，中序遍歷統一寫法-空指針標記法

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        
        st = [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()
                node.left, node.right = node.right, node.left
        return root

方法3-4：迭代法，中序遍歷統一寫法-boolean標記法

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        st = [(root, False)] if root else []

        while st:
            node, visited = st.pop()
            if visited:
                node.left, node.right = node.right, node.left
                continue
            
            if node.right:
                st.append((node.right, False))
            
            st.append((node, True))

            if node.left:
                st.append((node.left, False))
        
        return root

方法4-1：遞歸法，后序遍歷

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        self.invertTree(root.left)
        self.invertTree(root.right)
        root.left, root.right = root.right, root.left
        return root

方法4-2：迭代法，偽后序遍歷（結果是對的，看起來像是后序遍歷，實際上它是前序遍歷，只不過把中間節點處理邏輯放到了最后。還是要用'統一寫法'才是真正的后序遍歷）：

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        st = [root]
        while st:
            node = st.pop()
            if node.right:
                st.append(node.right)
            if node.left:
                st.append(node.left)
            node.left, node.right = node.right, node.left # 放到最后，依然是前序遍歷
        return root

方法4-3：迭代法，后序遍歷統一寫法-空指針標記法

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        
        st = [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()
                node.left, node.right = node.right, node.left
        return root

posted on 2025-09-02 19:27 axuu 閱讀(7) 評論(0) 收藏舉報