[演算法題目] Validate Binary Search Tree

本題資訊

難度：easy
使用語言：C++
相關概念：Binary Search Trees

題目敘述

Given a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Sample Input:

Sample Output:
true

目的很簡單，判斷二元樹是否有符合二元樹的定義。

Idea

這一題若熟悉二元樹定義，我想應該不會太難。主要是如何比大小，若是往左走的話，當前元素必須比父節點還要小，如果是往右走的話，當前元素必須比父節點還大（或是相等），若有不符合直接回傳 false。所以這裡會需要變數暫存上個元素的值。

class BST {
public:
  int value;
  BST *left;
  BST *right;

  BST(int val);
  BST &insert(int val);
};

bool checkNode(BST *node, int num1, int num2){
  if (node == nullptr)
    return true;
  if (num2 <= node->value || node->value < num1)
    return false;
  return checkNode(node->left, num1, node->value) && checkNode(node->right, node->value, num2);
}

bool validateBst(BST *tree) {
  return checkNode(tree, INT_MIN, INT_MAX);
}

時間複雜度：\(O(n)\)，\(n\) 是二元樹的節點個數。
空間複雜度：\(O(d)\)，\(d\) 是二元樹的高。（不太確定為什麼？）