Validate Binary Search Tree--LeetCode

╰半橙微兮° 2022-08-05 14:18 265阅读 0赞

题目：

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

Assume a 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.

思路：使用递归，或者中序遍历记录前向节点的值

  1. bool isValidBST(BinTree* root)
  2. {
  3.     if(root ==NULL)
  4.         return true;
  5.     else
  6.     {
  8.         if(root->right != NULL&& root->left == NULL)
  9.             return  isValidBST(root->right)&& root->value <root->right->value;
  10.         else if(root->left != NULL && root->right == NULL)
  11.             return isValidBST(root->left)&& root->value > root->left->value;
  12.         else if(root->left != NULL && root->right != NULL)
  13.             return isValidBST(root->right)&&isValidBST(root->left)&& root->value >root->left->value && root->value < root->right->value;
  14.         else
  15.             return true;    
  17.     }
  18. }

第二种方法和中序遍历非常相似，因为中序遍历的结果是有序的，记录前序节点，当前节点和前序节点相比较即可

  1. BinTree* cur=NULL,*pre= NULL;
  2. bool isValidBSTSecond(BinTree* root)
  3. {
  4.     if(root== NULL)
  5.         return true;
  6.     bool left = isValidBSTSecond(root->left);
  8.     if(pre == NULL)
  9.         pre = root;
  10.     cur = root;
  11.     if(cur != pre && pre->value > cur->value)
  12.         return false;        
  13.     pre = cur;
  15.     bool right =isValidBSTSecond(root->right);
  16.     return right&&left;
  19. }

发表评论

表情：
评论列表 （有 0 条评论，265人围观）

还没有评论，来说两句吧...

相关阅读