【LeetCode】226. Invert Binary Tree

Question link

Link

Intuition

Given the root of a binary tree, invert the tree, and return its root.
(給定一個二元樹，請翻轉整個樹)

1. Recursive
   • ✔️ Pre-order, NLR(Node-Left-Right)
   • ✔️ In-order, LNR(Left-Node-Right)
   • ✔️ Post-order, LRN(Left-Right-Node)
2. Queue(FIFO) 先訪問先處理

Approach

Recursive

1. 確認遞迴函數的回傳值與參數
   首先題目要要求返回經過翻轉後的二元樹的根節點，因此返回值為 TreeNode* ，傳入參數為 root
2. 確認中止遞迴的條件
   只要訪問到空的節點，就直接回傳 nullptr
3. 確認單層的遞迴邏輯
   因為是要交換一個節點下左右兩個子節點，因此在Preorder尋訪中，我們要先透過 swap 函數交換兩個左

在Inorder中的順序是先將左子樹進行翻轉，再翻轉根結點，因此未翻轉的右子樹此時變成左子樹，我們要將左子樹再翻轉一次

Queue

1. 使用 Queue 來進行 level-order traversal
2. 邏輯與 Recursive 解法差不多，只要交換訪問到的節點，就交換左右兩個子樹

Complexity

• Time complexity:
  $O(n)$
  
  $T(n)=2\times T(\frac{n}{2})+O(1)$
• Space complexity:
  $O(n)$
  • worse case:
    $O(n)$
  • best cast:
    $\log (n)$

Code

Solution 1 Recursive

Preorder

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        swap(root->left, root->right); // mid
        invertTree(root->left);        // left
        invertTree(root->right);       // right
        return root;
    }
};

Inorder

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        invertTree(root->left); // left
        swap(root->left, root->right); // mid
        invertTree(root->left); // right
        return root;
    }
};

Postorder

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        invertTree(root->left); // left
        invertTree(root->right); // right
        swap(root->left, root->right); // mid
        return root;
    }
};

Solution 2 Queue

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* front = q.front();
                q.pop();
                swap(front->right, front->left);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
        }
        return root;
    }
};