LeetCode Invert Binary Tree 二元樹反轉

本篇為LeetCode上演算法的簡單問題，Invert Binary Tree，二元樹反轉。

Invert a binary tree.

Example:

Input:

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

Output:

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

Trivia:

This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

這是很有名的題目，因為這題是Mac知名套件管理工具Homebrew作者Max Howell去Google面試所考的白板題，因為解不出來所以就沒被雇用了。

這題我沒看其他人的解答想一下也解出來了，所以有點讓我意外。

題目要求將二元樹中每個節點的子節點左右對調。看到這種樹結構的題目先想到的都是用遞迴解。

public static TreeNode invertTree(TreeNode root) {
    if(root == null || root.left == null && root.right == null) {
        return root;
    }
   
    TreeNode tmp = root.right;
    root.right = root.left;
    root.left = tmp;
    invertTree(root.left);
    invertTree(root.right);
   
    return root;
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

但其實最快的解法是，把白板翻過來就OK啦。

• 雖然我們公司 90%的工程師都用你開發的工具，但我們還是不聘用你
• LeetCode Merge Two Binary Trees 合併兩個二元樹