Zenn
😸

LeetCoding Challenge Oct.31: Recover Binary Search Tree

2020/11/01に公開
Java
LeetCode
tech

LeetCode October Challenge の 31 日目。

今日の問題は Recover Binary Search Tree。

問題の概要

  • 二箇所のノードが入れ違っている二分探索木が与えられるので、その入れ違いを修復する
  • ただし木の構造を変更してはならない

考え方

  • これは Hard 問題らしいけど、二分探索木を理解していればさほど難しくないのでは… 🤔
    • 二分探索木の各ノードを通りがけ順 (inorder) で辿ると、値を昇順に列挙できるね！
    • 値を列挙できれば、隣同士を比較して大小関係が逆転している箇所を見つけだせるぞ 💪
  • 値の入れ違いのパターンは二種類ある
    • 入れ違った値が隣り合っているケース
      • Fig.1
    • 入れ違った値が離れているケース
      • Fig.2
    • 入れ違いにより、隣同士の大小関係が逆転する箇所は多くても 2 箇所に限られるね
  • まずは空間計算量 O(n) のアルゴリズムを考えてみよう
    • 通りがけ順でノードを List<TreeNode> 的なリストに詰める
    • リストができてしまえば、あとは大小関係が逆転している箇所を探し出すだけ
      • 1 箇所だけなら、その値を入れ替える
      • 2 箇所あれば、一番左寄りの値と一番右寄りの値を入れ替える
  • ではこれと同様のことを、リストを使わずに実現するには？
    • 二分探索木を通りがけ順で辿る際に、常に「一つ左隣のノード」を保持すれば OK
  • 二分探索木を辿る方法としては、再帰を用いる方法とスタックを用いる方法の 2 つがある
    • いずれにしても、バランスの悪い二分探索木など最悪ケースの場合には O(n) の空間計算量となってしまうが、これは致し方ない…
  • まずは再帰を用いて実装 → accept 👍
    • Runtime 2ms で Your runtime beats 84.07 % of java submissions.
    • あと 1ms 及ばず…
  • ちょっと工夫を凝らしてみよう
    • 大小関係が逆転する箇所が 2 箇所見つかったら、その時点で処理を打ち切ることができるぞ！
      • これを実現しようとすると、スタックを使った実装の方がよさそう
  • 続いてスタックを用いて実装 → accept
    • こちらも 2ms 😭
    • これ以上はちょっとネタがないのでここで諦めよう…

コード

再帰を用いた実装

class Solution {
    public void recoverTree(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        retrieve(root, null, result);

        int t = result.get(0).val;
        if (result.size() == 2) {
            result.get(0).val = result.get(1).val;
            result.get(1).val = t;
        } else {
            result.get(0).val = result.get(3).val;
            result.get(3).val = t;
        }
    }

    TreeNode retrieve(TreeNode node, TreeNode prev, List<TreeNode> result) {
        if (node.left != null) {
            TreeNode l = retrieve(node.left, prev, result);
            if (l != null) {
                prev = l;
            }
        }

        if (prev != null && prev.val > node.val) {
            result.add(prev);
            result.add(node);
        }

        if (node.right != null) {
            return retrieve(node.right, node, result);
        }

        return node;
    }
}

スタックを用いた実装

class Solution {
    private static TreeNode DUMMY = new TreeNode(Integer.MIN_VALUE);
    private static TreeNode[] stack = new TreeNode[1000];

    public void recoverTree(TreeNode node) {
        TreeNode prev = DUMMY;
        int top = 0;
        TreeNode n1 = null, n2 = null;

        while (node != null || top > 0) {
            if (node != null) {
                stack[top++] = node;
                node = node.left;
                continue;
            }

            node = stack[--top];
            if (prev.val > node.val) {
                n2 = node;
                if (n1 != null) {
                    break;
                }
                n1 = prev;
            }

            prev = node;
            node = node.right;
        }

        int t = n1.val;
        n1.val = n2.val;
        n2.val = t;
    }
}

Discussion