Leetcode 226. Invert Binary Tree

Invert Binary Tree : 翻轉Binary Tree

Python

方法一 :（DFS）遞歸

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)  #左右子樹交換
        return root

方法二 : stack(棧)

class Solution(object):
    def invertTree(self, root):

        stack = []
        stack.append(root)
        while stack:
            node = stack.pop()   #pop一個值出來交換左右子樹
            if not node:
                continue
            node.left, node.right = node.right, node.left #左右子樹交換
            stack.append(node.left)
            stack.append(node.right)
        return root

C++

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) {
            return NULL;
        }
        
        // 遞歸翻轉左右子樹
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        
        // 交換左右子樹
        root->left = right;
        root->right = left;
        
        return root;
    }
};