題目

https://leetcode.com/problems/invert-binary-tree/

Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解答

C#

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        if (root == null)
            return root;

        TreeNode tmpLeft = root.left;
        TreeNode tmpRight = root.right;

        root.left = InvertTree(tmpRight);
        root.right = InvertTree(tmpLeft);

        return root;
    }
}

結果

Runtime: 92 ms, faster than 93.51% of C# online submissions.

Memory Usage: 23.1 MB, less than 20.0% of C# online submissions.

Time Complexity: O(n)

Space Complextiy: O(n)

為什麼我要這樣做？

趁對 tree 還有熱度時，我再多寫幾題與 tree 有關的題目
還記得 tree 是什麼嗎？可以參考以下文章 ↓
[Day 22] 演算法刷題 LeetCode 101. Symmetric Tree (Easy) Part 1 - Recursion
[Day 23] 演算法刷題 LeetCode 101. Symmetric Tree (Easy) Part 2 - Iteration
[Day 24] 演算法刷題 LeetCode 104. Maximum Depth of Binary Tree (Easy)
[Day 25] 演算法刷題 LeetCode 543. Diameter of Binary Tree (Easy)

這題主要是將原有的 tree 反轉，就像是照鏡子一樣

1. 判斷 root 是否為 null，若為 null 回傳 root;
2. 宣告 TreeNode tmpLeft 為 root.left;
3. 宣告 TreeNode tmpRight 為 root.right;
4. 此時使用遞迴將所有 TreeNode 對調
   • root.left = InvertTree(tmpRight);
   • root.right = InvertTree(tmpLeft);
   • 對調完成後回傳 root

以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉