c/c++开发分享C++实现LeetCode(98.验证二叉搜索树)

[leetcode] 98. validate binary search tree 验证二叉搜索树given a binary tree, determine if it is a valid bi


[leetcode] 98. validate binary search tree 验证二叉搜索

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.

example 1:

input:
2
/
1   3
output: true

example 2:

    5
/
1   4
/
3   6
output: false
explanation: the input is: [5,1,4,null,null,3,6]. the root node’s value
is 5 but its right child’s value is 4.

这道验证二叉搜索树有很多种解法,可以利用它本身的性质来做,即左<根<右,也可以通过利用中序遍历结果为有序数列来做,下面我们先来看最简单的一种,就是利用其本身性质来做,初始化时带入系统最大值和最小值,在递归过程中换成它们自己的节点值,用long代替int就是为了包括int的边界条件,代码如下:

c++ 解法一:

  // recursion without inorder traversal  class solution {  public:      bool isvalidbst(treenode* root) {          return isvalidbst(root, long_min, long_max);      }      bool isvalidbst(treenode* root, long mn, long mx) {          if (!root) return true;          if (root->val <= mn || root->val >= mx) return false;          return isvalidbst(root->left, mn, root->val) && isvalidbst(root->right, root->val, mx);      }  };

java 解法一:

  public class solution {      public boolean isvalidbst(treenode root) {          if (root == null) return true;          return valid(root, long.min_value, long.max_value);      }      public boolean valid(treenode root, long low, long high) {          if (root == null) return true;          if (root.val <= low || root.val >= high) return false;          return valid(root.left, low, root.val) && valid(root.right, root.val, high);      }  }

这题实际上简化了难度,因为有的时候题目中的二叉搜索树会定义为左<=根<右,而这道题设定为一般情况左<根<右,那么就可以用中序遍历来做。因为如果不去掉左=根这个条件的话,那么下边两个数用中序遍历无法区分:

   20       20
/          
20           20

它们的中序遍历结果都一样,但是左边的是 bst,右边的不是 bst。去掉等号的条件则相当于去掉了这种限制条件。下面来看使用中序遍历来做,这种方法思路很直接,通过中序遍历将所有的节点值存到一个数组里,然后再来判断这个数组是不是有序的,代码如下:

c++ 解法二:

  // recursion  class solution {  public:      bool isvalidbst(treenode* root) {          if (!root) return true;          vector<int> vals;          inorder(root, vals);          for (int i = 0; i < vals.size() - 1; ++i) {              if (vals[i] >= vals[i + 1]) return false;          }          return true;      }      void inorder(treenode* root, vector<int>& vals) {          if (!root) return;          inorder(root->left, vals);          vals.push_back(root->val);          inorder(root->right, vals);      }  };

java 解法二:

  public class solution {      public boolean isvalidbst(treenode root) {          list<integer> list = new arraylist<integer>();          inorder(root, list);          for (int i = 0; i < list.size() - 1; ++i) {              if (list.get(i) >= list.get(i + 1)) return false;          }          return true;      }      public void inorder(treenode node, list<integer> list) {          if (node == null) return;          inorder(node.left, list);          list.add(node.val);          inorder(node.right, list);      }  }

下面这种解法跟上面那个很类似,都是用递归的中序遍历,但不同之处是不将遍历结果存入一个数组遍历完成再比较,而是每当遍历到一个新节点时和其上一个节点比较,如果不大于上一个节点那么则返回 false,全部遍历完成后返回 true。代码如下:

c++ 解法三:

  class solution {  public:      bool isvalidbst(treenode* root) {          treenode *pre = null;          return inorder(root, pre);      }      bool inorder(treenode* node, treenode*& pre) {          if (!node) return true;          bool res = inorder(node->left, pre);          if (!res) return false;          if (pre) {              if (node->val <= pre->val) return false;          }          pre = node;          return inorder(node->right, pre);      }  };

当然这道题也可以用非递归来做,需要用到栈,因为中序遍历可以非递归来实现,所以只要在其上面稍加改动便可,代码如下:

c++ 解法四:

  class solution {  public:      bool isvalidbst(treenode* root) {          stack<treenode*> s;          treenode *p = root, *pre = null;          while (p || !s.empty()) {              while (p) {                  s.push(p);                  p = p->left;              }              p = s.top(); s.pop();              if (pre && p->val <= pre->val) return false;              pre = p;              p = p->right;          }          return true;      }  };

java 解法四:

  public class solution {      public boolean isvalidbst(treenode root) {          stack<treenode> s = new stack<treenode>();          treenode p = root, pre = null;          while (p != null || !s.empty()) {              while (p != null) {                  s.push(p);                  p = p.left;              }              p = s.pop();              if (pre != null && p.val <= pre.val) return false;              pre = p;              p = p.right;          }          return true;      }  }

最后还有一种方法,由于中序遍历还有非递归且无栈的实现方法,称之为 morris 遍历,可以参考博主之前的博客 binary tree inorder traversal,这种实现方法虽然写起来比递归版本要复杂的多,但是好处在于是 o(1) 空间复杂度,参见代码如下:

c++ 解法五:

  class solution {  public:      bool isvalidbst(treenode *root) {          if (!root) return true;          treenode *cur = root, *pre, *parent = null;          bool res = true;          while (cur) {              if (!cur->left) {                  if (parent && parent->val >= cur->val) res = false;                  parent = cur;                  cur = cur->right;              } else {                  pre = cur->left;                  while (pre->right && pre->right != cur) pre = pre->right;                  if (!pre->right) {                      pre->right = cur;                      cur = cur->left;                  } else {                      pre->right = null;                      if (parent->val >= cur->val) res = false;                      parent = cur;                      cur = cur->right;                  }              }          }          return res;      }  };

到此这篇关于c++实现leetcode(98.验证二叉搜索树)的文章就介绍到这了,更多相关c++实现验证二叉搜索树内容请搜索<猴子技术宅>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<猴子技术宅>!

需要了解更多c/c++开发分享C++实现LeetCode(98.验证二叉搜索树),都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/674051.html

发表评论

邮箱地址不会被公开。 必填项已用*标注