網頁

2018/12/21

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啦。


1 則留言: