6
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2018-09-30

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

はじめに

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

このツイートは現地シリコンバレーでは賛否両論です。シリコンバレーのテック業界では、面接試験の大部分がアルゴリズムの問題をその場で解けるか否かが判断基準になります。過去の経歴を見て書類選考は通過するものの、面接ではその場面のパフォーマンスを見られます。
すべての候補者は面接の場では平等な立場になれる、という点ではフェアなのですが、こういったアルゴリズムの問題はその場の空気とか候補者の緊張度合いとかで、解けるか否かが変わってきます。
私はアルゴリズムの問題を解くのがそこまで得意ではないので、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;
    }
6
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?