Validate Binary Search Tree

この文章ではleetcodeのValidate Binary Search Tree問題について議論します.

問題リンク:Validate Binary Search Tree2

ソリューション:source code2

1.問題分析

与えられた問題を簡単に以下に要約する.
バイナリ検索ツリー(BST)のルートディレクトリ.このBSTが正しく構成されているかどうかを確認します(i.e.ノードXの左側のサブツリーにはノードXより小さい値しかなく、右側のサブツリーにはノードXより大きい値しかありません).

2.最も愚かな草

一部のテーマは「最も愚かな解答」であるが,アルゴリズムを学習する際には,最も愚かな解答から最も知能的な解答まで,構想を整理する過程が重要である.
だから、この節では、「最も愚かな答え」を指摘しなければならない.
最も愚かな解決策は、与えられたBSTをinorder traversalに設定し、アクセス順にノードの値を記録し、巡視が完了した後に記録されたノードが昇順に配列されているかどうかを確認することである.
一時的に道を変える...
筆者の場合はもっと馬鹿で、このような考えはなく、그냥 각 노드별로 왼쪽 자식엔 자기보다 작은 값이, 오른쪽 노드에는 보자기다 큰 값이 있으면 되는거 아니야?シャベルを使っています.
賢い読者はすでに知っているかもしれませんが、上記の考えには下図に示す反例があります.
下図に示すように、ノード4とノード7は、いずれも左側に小さな値を持つノード、右側に大きな値を持つノードである.
有効に見えるが、ノード3は右側のサブツリーに位置するため、有効なBSTではない.

より厳密な定義が好きな読者には、このような疑問があるかもしれません.valid한 BST를 inorder traversal하면 오름차순으로 정렬된 기록이 얻어진다는 것은 알겠어. 근데 오름차순으로 정렬된 기록이 얻어졌다고해서 valid한 BST였다고 이해해도 되는걸까?要約すると、valid한 BST를 inorder traversal하면 오름차순으로 정렬된 기록이 얻어진다も成立しているかどうかの疑問です.
これは簡単に証明できますが、次の証明書をフォローしてみてください.

inorder遍歴により得られた配列をarr[0:len]と呼び、このときarr[0:len]は昇順に配列されている(arr[x:y]はPythonと同じ言語における開閉区間を表す).

任意の要素arr[i](0<=iBST内の

値を有するノードが左側のサブツリーを有する場合、それらは、inorderループが行われているため、アレイ内のarr[i]内に存在する.

しかし、arr[0:i]がソートされていると仮定すると、arr[0:len]内のすべての値はarr[0:i]ステップ未満である.

したがって、BSTに

の値を持つノードの左側のサブツリーがある場合、これらのノードの値はいずれもarr[i]未満である.

右サブツリーについても同様に証明できる.(証明書終了)

要するに、上記の考えをコードに移すと、以下のようになります.

class Solution
{
public:
  std::vector<int> visit_log_;

  void TraverseInorder(TreeNode* root)
  {
    if (!root)
    {
      return;
    }

    TraverseInorder(root->left);
    visit_log_.push_back(root->val);
    TraverseInorder(root->right);
  }

  bool isValidBST(TreeNode* root)
  {
    visit_log_.clear();

    TraverseInorder(root);

    for (std::size_t idx = 1; idx < visit_log_.size(); ++idx)
    {
      if (visit_log_[idx - 1] >= visit_log_[idx])
        return false;
    }

    return true;
  }
};

上図は速度23%、メモリ36%を示しています.
与えられた解がツリー内のノード数がnnnである場合、inorderループは、得られたアクセス記録が昇順であるか否かを決定するために、O(n)O(n)O(n)O(n)O(n)O(n)O(n)O(n)O(2 n)=O(n)O(2 n)=O(n)O(2 n)=O(2 n)=O(2 n)=O(2 n)=O(n)=O(n)の時間的複雑さを調べる.
また,アクセス順序を記録するためにarr[i]ベクトルが作成され,arr[i]の空間的複雑さを有する.

3.適切で賢い解答

本節では,第2節におけるO(n)O(n)O(n)O(n)の空間的複雑さをO(1)O(1)O(1)に設定することを試みる.
実際によく考えてみると、訪問順を全て単独で記録する必要はなく、ツアー終了後に上昇順を判断します.
現在のアクセスノードの値が以前にアクセスしたノードより大きいかどうかを観察することによって,inorderループを実行するだけで,第2節アルゴリズムの空間的複雑さを改善する.

class Solution
{
public:
  bool is_first_visit_ = true;
  int last_visited_number_;

  bool isValidBST(TreeNode* root)
  {
    if (!root)
    {
      return true;
    }

    if (!isValidBST(root->left))
    {
      return false;
    }

    if (!is_first_visit_ && last_visited_number_ >= root->val)
    {
      return false;
    }

    is_first_visit_ = false;
    last_visited_number_ = root->val;

    if (!isValidBST(root->right))
    {
      return false;
    }

    return true;
  }
};

特に改善はありませんが、上記のプールを使用する速度は98%、メモリは98%です.
92%のパーセントが得られます.
備考)原因はわかりませんが、この問題に対しては、点数ごとのパーセンテージが大きくずれています.ランダム入力の問題なのか、スコアサーバの状態なのか...まず白粉の上に意味を置かないでください.
O(2 n)O(2 n)O(2 n)O(2 n)O(n)O(n)O(n)O(n)NがO(n)O(n)からO(1)O(1)O(1)O(1)に改善されると理解できる.

4.大したことはないが、試してみる価値のある答え

この部分では、ぜひ練習したいという欲求を生んだクイズをまとめました.
3節のアルゴリズムが少し残念であれば,再帰を頻繁に呼び出す可能性がある.
この節では,第3節と同様の方法を用いるが,再帰を解放しスタックを利用することによって実現を試みる.
tail再帰形式を有する再帰アルゴリズムを繰り返し文として解くのは簡単であるが,inorder遍歴のような形式の再帰アルゴリズムを繰り返し文として解くのは意外に困難である.
いずれの形式の再帰コードにおいても,システム的に繰返し文形式に変換する方法は存在するが,この位置決めではより定性的な方法で変換を試みた.
システムの方法については後で機会があれば他の宣伝で検討します

class Solution
{
public:
  bool is_first_visit_ = true;
  int last_visited_number_;

  bool isValidBST(TreeNode* root)
  {
    TreeNode* called = root;
    std::stack<TreeNode*> to_be_returned;

    while (true)
    {
      if (called)
      {
        to_be_returned.push(called);
        called = called->left;
      }
      else
      {
        if (to_be_returned.empty())
        {
          break;
        }

        TreeNode* activated = to_be_returned.top();

        if (!is_first_visit_ && last_visited_number_ >= activated->val)
        {
          return false;
        }
        is_first_visit_ = false;
        last_visited_number_ = activated->val;

        called = activated->right;

        to_be_returned.pop();
      }
    }

    return true;
  }
};

備考)前述したようにパーセンテージはあまり意味がないので,その解答のパーセンテージは付加されていない.少なくとも他の方法に比べて、これは屈服しない解答である.