0226. Invert Binary Tree - chasel2361/leetcode GitHub Wiki

Given the root of a binary tree, invert the tree, and return its root.

Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
exmple1

Example 2:
Input: root = [2,1,3]
Output: [2,3,1]
example2

Example 3:
Input: root = []
Output: []

Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

這題可以用遞迴做，也可以用迭代做
遞迴的程式碼寫起來比較簡單，基本上就是父節點把左右子節點交換後，再將左右子節點帶進函式開啟遞迴，直到帶入韓式的節點為 None 為止，程式碼如下：

python

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root){
            std::swap(root->right, root->left);
            invertTree(root->right);
            invertTree(root->left);
        }
        return root;
    }
};

這樣寫的時間複雜度為 O(N)，因為每個節點都只要走一遍就可以，
空間複雜度在二元樹平衡的狀態下會是 O(logN)

迭代的寫法會應用到之前 BFS 的寫法(基本上遞迴就是 DFS 的概念)，要使用一個 FIFO 的資料結構儲存每層的節點，再逐一把節點的子節點左右交換，直到 FIFO 的資料結構空了(沒有下一層節點)為止，寫成程式碼如下：

python

# 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
from collections import deque
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: return None
        q = deque([root])
        while q:
            ptr = q.pop()
            ptr.left, ptr.right = ptr.right, ptr.left
            if ptr.left: q.appendleft(ptr.left)
            if ptr.right: q.appendleft(ptr.right)
        return root

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return NULL;
        std::queue<TreeNode*> q;
        
        q.push(root);
        while (q.size() > 0){
            TreeNode* ptr = q.front();
            q.pop();
            std::swap(ptr->left, ptr->right);
            if (ptr->left) q.push(ptr->left);
            if (ptr->right) q.push(ptr->right);
        }
        return root;
    }
};

這樣寫的時間複雜度會是 O(N)，一樣，每個節點都要走一遍 空間複雜度則是 O(N)， 受到單層總節點數決定。

⚠️ **GitHub.com Fallback** ⚠️