LeetCode 75 Level 1 - Day 8 Binary Search Tree

98. Validate Binary Search Tree

• 題目連結
• 難易度：Medium

題目敘述

Given the root of 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.

預設函數

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool isValidBST(struct TreeNode* root){

}

題目限制

• The number of nodes in the tree is in the range .
• <= Node.val <=

解題過程及程式碼

本題是 Binary Search Tree 的第一題，題目給一個二元搜尋樹 (Binary Search Tree)，要確認是否滿足二元搜尋樹條件，如下圖所示 (來源: Leetcode)，就不滿足第 2 點，看到 (4) 比 (5) 本身來的小。

• 左子節點要比節點本身小。
• 右子節點要比節點本身大。
• 每個左子節點和右子節點都要是二元搜尋樹 (滿足上述2點)。

想法是使用二元樹的中序走訪 （Inorder Traversal），對於滿足條件的二元搜尋樹會產生一個從小到大的順序，將走訪結果丟入隊列 queue 中，再拿出來檢查

• 複習二元樹中的中序走訪 （Inorder Traversal）

  void print_inorder(node *ptr) {
      if (ptr != NULL) {
          print_preorder(ptr->left);     // 先處理左子節點
          printf("[%2d]\n", ptr->data);  // 再處理印自己
          print_preorder(ptr->right);    // 最後處理右子節點
      }
  }
  

• 程式碼上傳

  #define MAX_QUEUE_SIZE 10000
  
  int *queue, *front, *rear, *counter;
  
  bool isValidBST(struct TreeNode* root){
      int dq1 = 0, dq2 = 0;
  
      queue = (int*)calloc(MAX_QUEUE_SIZE, sizeof(int));
      front = (int*)malloc(sizeof(int));
      rear = (int*)malloc(sizeof(int));
      counter = (int*)malloc(sizeof(int));
  
      *front = *rear = *counter = 0;
  
      /* 中序走訪每個節點丟到 queue 裡 */
      run_inorder(root);
  
      if (*counter == 1) {
         return 1;
      }
  
      dq1 = deleteq();
      /* 取出 queue 檢查是否由小到大 */
      for (int i=0; i<(*counter)-1; i++) {
          dq2 = deleteq();
          if (dq2 > dq1) {
              dq1 = dq2;
          } else {
              return 0;
          }
      }
      return 1;
  }
  
  void run_inorder(struct TreeNode* ptr) {
      if (ptr != NULL) {
          run_inorder(ptr->left);   // 先是左子節點
          addq(ptr->val);           // 再來是自身
          (*counter)++;
          run_inorder(ptr->right);  // 最後是右子節點
      }
  }
  
  void addq(int val) {
      *rear = (*rear + 1) % MAX_QUEUE_SIZE;
      queue[*rear] = val;
  }
  
  int deleteq(void) {
      *front = (*front + 1) % MAX_QUEUE_SIZE;
      return queue[*front];
  }
  

第一次參加，沒想過能堅持15天了，謝謝看到這邊的朋友!