Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Medium 98. Validate Binary Search Tree

leetcode
tags: leetcode

問題

二分木を与えられた時, それが正しい二分探索木(BST)か決めなさい

BSTが以下のように定義されると仮定しなさい

  1. あるノードの左部分木はそのノードの値よりも小さい値のノードしか持っていない

  2. あるノードの右部分着はそのノードの値よりも大きい値のノードしか持っていない

  3. 左右の部分木も両方共BSTでなければならない

解法1(recursive)

BSTの再帰的な定義に従って根から葉まで辿って行けば良いです

  • 基底は葉であること
  • ノードが左もしくは右に子ノードを持っていればそこを根とする木としてから探索します

LeetCodeをやっていて学んだこと(?)はC++ではINT_MAXやINT_MINはコーナーケースで落ちやすいということです

なのでできるだけこれを使わないような実装を心がけたい(Pythonならfloat('inf')を使えば大丈夫です)

計算量

ノードの数を$n$とすると

  • 空間計算量はノードをちょうど1回訪れるので$O(n)$
  • 時間計算量は同様の理由で$O(n)$

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
      def helper(root, lower = -float('inf'), upper = float('inf')):
        if not root:
          return True
        
        if root.val <= lower or upper <= root.val:
          return False
        if not helper(root.right, root.val, upper):
          return False
        if not helper(root.left, lower, root.val):
          return False
        return True
      
      return helper(root)

C++

もしPythonと同じようにINT_MAXなどを使うと根の値がINT_MAXであるときに謝るので注意

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isValidBST(TreeNode* root) {
    return helper(root, NULL, NULL);
  }
private:
  bool helper(TreeNode* node, TreeNode* lower, TreeNode* upper) {
    if (!node) {
      return true;
    }
    if ((lower && node->val <= lower->val) || (upper && upper->val <= node->val)) {
      return false;
    }
    return helper(node->left, lower, node) && helper(node->right, node, upper);
  }
};

解法2(iterative)

上の解法はいわゆるDFS(深さ優先探索)です

Stackというデータ構造を用いて同じ探索が実現できます

上と同様に解いているのでPythonとC++では解き方が多少違います

計算量

  • 空間計算量は最悪ノードと同じ数だけのサイズになるので$O(n)$
  • 時間計算量はノードを訪れる回数はrecursiveな解き方と同じなので$O(n)$

Python

Stackに根と最小値, 最大値を積みます

Stackが空になるまで左右の部分木を走査します

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
      if not root:
        return True
      
      stack = [(root, float('-inf'), float('inf'))]
      while stack:
        root, lower, upper = stack.pop()
        if not root:
          continue
        if root.val <= lower or upper <= root.val:
          return False
        stack.append((root.right, root.val, upper))
        stack.append((root.left, lower, root.val))
      return True

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isValidBST(TreeNode* root) {
    if (!root) {
      return true;
    }
    stack<tuple<TreeNode*, TreeNode*, TreeNode*>> stk;
    TreeNode *minNode = NULL, *maxNode = NULL;
    stk.push(make_tuple(root, minNode, maxNode));
    while (stk.size()) {
      auto tmp = stk.top();
      stk.pop();
      root = get<0>(tmp);
      TreeNode* lower = get<1>(tmp);
      TreeNode* upper = get<2>(tmp);
      if (!root) {
        continue;
      }
      if ((lower && root->val <= lower->val) || (upper && upper->val <= root->val)) {
        return false;
      }
      stk.push(make_tuple(root->left, lower, root));
      stk.push(make_tuple(root->right, root, upper));
    }
    return true;
  }
};

解法3(Inorder traversal)

木の探索順序

木を探索する際の順序として以下の図ように

  • Inorder(左→根→右)
  • Preorder(根→左→右)
  • Postorder(左→右→根)

があります

ノードが5つの木の場合を図示すると以下の通りです

Inorderで探索すると

二分木をInorderで探索すると小さい要素から見ていくことになります

そのため, 前に探索したノードの値を保持してその値よりも現在のノードの値の方が大きいということを確認すれば良いわけです

Stackをここでも使います

  • Stackでどんどん左のノードに行って遡ったノードを入れる
  • これ以上入れられない(左ノードがNULL相当)時にそこから左, 右, 根の順番で大きさを比べます

計算量

recursive, iterativeどちらでも解けます

どちらも本質的には上で行っている探索と同じであり, 計算量も同じです

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
      prev, cur, stack = None, root, []
      while stack or cur:
        while cur:
          stack.append(cur)
          cur = cur.left
        top = stack.pop()
        if prev and top.val <= prev.val:
          return False
        prev, cur = top, top.right
      return True

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isValidBST(TreeNode* root) {
    TreeNode *prev = NULL, *cur = root;
    stack<TreeNode*> stk;
    while (stk.size() || cur) {
      while (cur) {
        stk.push(cur);
        cur = cur->left;
      }
      TreeNode* top = stk.top();
      stk.pop();
      if (prev && top->val <= prev->val) {
        return false;
      }
      prev = top, cur = top->right;
    }
    return true;
  }
};

ちなみに

Inorderでの実装では空間計算量は最適化すると$O(1)$で済むはずです

  • 常に前のノードが最小の値を持つ
    • 前のノードさえ保持していれば良い
  • iterativeに実装する
    • 再帰だと実行回数から$O(n)$になってしまいますが, 反復だと変数として使うのは前のノードのみ

実装は時間が出来たらすることにします