【leetcode 完整解答】226. Invert Binary Tree

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]

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints:

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

解答:

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

root.left, root.right = root.right, root.left 形成 tuple,把 左邊的 root 和右邊的 root 交換。

self.invertTree(root.left)
self.invertTree(root.right)

對左邊的小數遞迴後,再對左邊的小數遞迴。

也可以這樣寫:

先反轉小樹,再反轉自己。


self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left

解答2:

def invertTree(self, root):
    if root:
        invert = self.invertTree
        root.left, root.right = invert(root.right), invert(root.left)
        return root

跟解答1 的邏輯一樣,把解答一樣,不過把解答1 的步驟省略。

更簡短的寫法:

def invertTree(self, root):
    if root:
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

其他:

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

Python 也有另外一種寫法,交換、呼叫、遞迴,這種寫法不需要實例物件 self。

接下來介紹 C 語言的寫法:

python 用 None 表達,C 語言用 NULL。

C 先放型態,再放變數名稱 Python 先放變數名稱,再放型態。

C 語言沒辦法和 Python 一樣,C 語言需要 temp 才能完成數值交換的動作。

由於 struct TreeNode* root 中 TreeNode 的結尾是 * ,因此用 ->,如果為 struct TreeNode* root ,則和 python 一樣,以 root.left 表示。

struct TreeNode* invertTree(struct TreeNode* root){
    if(root==NULL){
        return NULL;
    }
    invertTree(root-> left);
    invertTree(root-> right);
    struct TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    return root;
}

Leave a Comment

Your email address will not be published. Required fields are marked *