LeetCode: Invert Binary Tree (homebrewの作者がGoogle面接試験で遭遇した問題)

Invert Binary Tree の解説です。
https://leetcode.com/problems/invert-binary-tree/description/

はじめに

homebrewのクリエーターMax Howell は、Googleの面接試験でこの問題に当たったらしく、この問題を解けなかったため面接に落とされたそうです。下記、Maxのツイートです。

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

— Max Howell (@mxcl) June 10, 2015

このツイートは現地シリコンバレーでは賛否両論です。シリコンバレーのテック業界では、面接試験の大部分がアルゴリズムの問題をその場で解けるか否かが判断基準になります。過去の経歴を見て書類選考は通過するものの、面接ではその場面のパフォーマンスを見られます。
すべての候補者は面接の場では平等な立場になれる、という点ではフェアなのですが、こういったアルゴリズムの問題はその場の空気とか候補者の緊張度合いとかで、解けるか否かが変わってきます。
私はアルゴリズムの問題を解くのがそこまで得意ではないので、Maxさんの意見にやや賛成したい気分ではあります。かといってMaxさんのような素晴らしい経歴はもってないので、候補者をフェアに扱ってもらえる現在のシリコンバレーの面接のデファクトスタンダードに恩恵を受けているのも事実です。
うーん、難しい。。。

Problem statement

Invert a binary tree.

Example:

Input:

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

Output:

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

My solution

問題文の指定がなかったため、Treeのコピーをつくらないといけないのか？と思い、せっせとTreeのコピーを作成していました。。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // Create pointer to root node
        TreeNode head = new TreeNode(0);
        head.right = new TreeNode(root.val);
        TreeNode copy = head.right;
        helper(copy, root.right, true);
        helper(copy, root.left, false);
        return head.right;
    }

    public void helper(TreeNode copy, TreeNode node, boolean isRight) {
        if (node == null) {
            return;
        }
        TreeNode next = null;
        if (isRight) {
            copy.left = new TreeNode(node.val);
            next = copy.left;
        } else {
            copy.right = new TreeNode(node.val);
            next = copy.right;
        }
        helper(next, node.right, true);
        helper(next, node.left, false);
    }
}

Optimal Solution

TreeNodeのインスタンスをMutationして良い場合、かなり簡潔にできるそうです。気づかなかった。。
参照 https://www.programcreek.com/2014/06/leetcode-invert-binary-tree-java/

Recursive solution

単にHelper関数の中で、Treeの左右をスワップするだけです。
Time Complexity = O(N): すべてのTreeを走査する必要があるため
Space Complexity = 1: 新たにスペースを作っていないため

    public TreeNode invertTree(TreeNode root) {
        if (root != null) {
            helper(root);
        }
        return root;
    }

    public void helper(TreeNode node) {
        if (node == null) {
            return;
        }
        TreeNode tmp = node.right;
        node.right = node.left;
        node.left = tmp;
        helper(node.right);
        helper(node.left);
    }

Iterative solution

面接では必ず、IterativeとRecursiveの両方を聞かれるため、Iterativeのコードも書いておきます。
Queueを使って、Treeの要素のアクセスしていきます。

Time Complexity = O(N): すべてのTreeを走査する必要があるため
Space Complexity = O(N)?: Queueを作成しているため、その分のスペースは最低限必要になる

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur.right != null) {
                queue.add(cur.right);
            }
            if (cur.left != null) {
                queue.add(cur.left);
            }
            TreeNode tmp = cur.right;
            cur.right = cur.left;
            cur.left = tmp;
        }
        return root;
    }