LeetCode 98. Validate Binary Search Tree( 遞歸，BST )

• 2020 年 2 月 14 日
• 筆記

題意：判斷一個二叉樹是否為 二叉搜索樹BST

題解：所有思路都是去找二叉樹中不滿足BST性質的節點，找到了，就不符合，找不到就符合。那麼怎麼去找呢？我提供兩種思想。

第一個是，BST的中序遍歷是一個有序數組，所以把BST 中序遍歷的結果拿出來，看看是不是有序的就可以了。很簡單。那如果不讓你用額外的空間呢？那就在中序遍歷的過程中，判斷是不是有序。我們維護一個值last，這個值是遍曆數組的前一個元素，如果發現有當前元素小於前一個元素，就是false

第二個思路是，判斷每個節點是否符合區間。這種方法隨便哪種遍歷都可以。根節點的區間，是沒有限制的，Int.Min ~ Int.Max。那麼左子節點就是Int.Min ~ root->val ，那麼左子節點的右子節點，就是root->left->val，root->val。綜上所述，每遍歷到一個節點時，它的區間的最小值或者最大值都要變成它父親節點的值，這取決於左子樹還是右子樹。

這道題目的坑點是，數據範圍是 -(1<<31) ~ (1<<31)-1 ,就是int的邊界值。

解法一：

 int father = -1*(1<<31);      int tag=-1;      bool isValidBST(TreeNode* root) {          if(root==NULL)              return true;          if(isValidBST(root->left))          {              if(root->val>father||(tag==-1&&root->val==father))              {                  father = root->val;                  tag=1;                  return isValidBST(root->right);              }          }          return false;      }

第二種

/**   * 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==NULL)              return true;         return fun(root,NULL,NULL);        }        bool fun(TreeNode* root,TreeNode* min,TreeNode* max)      {            if(root->left!=NULL)          {            if(!fun(root->left,min,root))              return false;          }            if(root->right!=NULL)          {            if(!fun(root->right,root,max))              return false;          }            if(((min!=NULL&&root->val>min->val)||(min==NULL)) &&(             (max!=NULL&&root->val<max->val )||(max==NULL)))              return true;          else              return false;          }    };