当前位置:   article > 正文

算法力扣刷题记录 五十四【98.验证二叉搜索树】

算法力扣刷题记录 五十四【98.验证二叉搜索树】

前言

二叉搜索树操作。继续。
记录 五十四【98.验证二叉搜索树】


一、题目阅读

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:
在这里插入图片描述

输入:root = [2,1,3]
输出:true
  • 1
  • 2

示例 2:
在这里插入图片描述

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
  • 1
  • 2
  • 3

提示:

树中节点数目范围在[1, 104] 内
-2^31 <= Node.val <= 2^31 - 1
  • 1
  • 2

二、参考学习

弯路

  1. 依然从递归下手。想返回左子树的最大值和返回右子树的最小值,再回到中间节点比较(左右中)。得到左子树的最大值,和中间节点比较,再得到右子树的最小值,和中间节点比较。(类似:中左右)。
  2. 思路缺陷:
  • 返回值如果定义最大值或最小值,和所求目标bool类型不符;
  • 逻辑不统一,左子树的最大值在右孩子上,右子树的最小值在左孩子上。
  • 如果同时操作左子树和右子树,那么比较对象不正确。
  • 所以,学习参考获取思路。

学习内容

参考学习链接

  1. 正确思路:对一个二叉搜索树中序遍历,可以得到有序递增数列。这是二叉搜索树特性,也是验证是否是二叉搜索树的方式。

  2. 递归法:递归法实现三种方式:

    1. 第一种:定义一个数组,在中序遍历过程中搜集数值;再对数组遍历,判断是否递增。代码实现:

      /**
       * Definition for a binary tree node.
       * struct TreeNode {
       *     int val;
       *     TreeNode *left;
       *     TreeNode *right;
       *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
       *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
       *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
       * };
       */
      class Solution {
      public:
          void traversal(TreeNode* cur,vector<int>& vec) {
              if(!cur) return;//终止条件叶子节点
              traversal(cur->left,vec);
              vec.push_back(cur->val);
              traversal(cur->right,vec);
              return;
          }
          bool isValidBST(TreeNode* root) {
              vector<int> vec;
              traversal(root,vec);
              for(int i = 1;i < vec.size();i++){
                  if(vec[i] <= vec[i-1]) return false;
              }
              return true;
          }
      };
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
    2. 第二种:定义全局变量,记录遍历过的最大值。相当于边遍历边比较。

      /**
       * Definition for a binary tree node.
       * struct TreeNode {
       *     int val;
       *     TreeNode *left;
       *     TreeNode *right;
       *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
       *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
       *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
       * };
       */
      class Solution {
      public:
          long long max_value = LONG_MIN;//长整型的最小值
          bool isValidBST(TreeNode* root) {
              //终止条件,中序遍历
              if(!root) return true;
              //左子树
              bool left = isValidBST(root->left);
              if(!left) return false;//如果左子树已经不是二叉搜索树,可以直接返回,没有也可以。
              //中
              if(max_value >= root->val) return false;
              max_value = root->val;
              //右
              bool right = isValidBST(root->right);
              return left && right;
          }
      };
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
    3. 第三种:题目如果节点数值包含长整型的最小值怎么办?没有比这个更小的,那么在if(max_value >= root->val)会出错。所以,最好不用全局变量,进一步优化,使用双指针,用一个指针记录前一个节点,比较逻辑在中间节点处完成

      /**
       * Definition for a binary tree node.
       * struct TreeNode {
       *     int val;
       *     TreeNode *left;
       *     TreeNode *right;
       *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
       *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
       *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
       * };
       */
      class Solution {
      public:
          TreeNode* pre = nullptr;
          bool isValidBST(TreeNode* root) {
              //终止条件
              if(!root) return true;
              //不为空,中序遍历
              bool left = isValidBST(root->left);//左
              if(!left) return false;
              //中
              if(pre!=nullptr && pre->val >= root->val){
                  return false;
              }
              pre = root;//更新
              //右
              bool right = isValidBST(root->right);
              return left && right;
      
          }
      };
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
      • 30
      • 31
  3. 迭代法:已经获取思路,进行中序遍历。那么中序遍历的迭代实现:记录 三十六【二叉树迭代遍历】 有两种方式,一个区别于前后序迭代,一个是统一迭代模版(空指针标记法)。

    1. 根据思路和统一迭代模版,代码实现:

      /**
       * Definition for a binary tree node.
       * struct TreeNode {
       *     int val;
       *     TreeNode *left;
       *     TreeNode *right;
       *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
       *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
       *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
       * };
       */
      class Solution {
      public:
          bool isValidBST(TreeNode* root) {
              stack<TreeNode*> st;
              if(!root) return true;
              st.push(root);
              TreeNode* pre = nullptr;
              while(!st.empty()){
                  TreeNode* cur = st.top();st.pop();
                  if(cur != nullptr){
                      if(cur->right) st.push(cur->right);//右
                      st.push(cur);//中
                      st.push(nullptr);//标记
                      if(cur->left) st.push(cur->left);
                  }else{
                      TreeNode* node = st.top();st.pop();
                      if(pre != nullptr && pre->val >= node->val){
                          return false;
                      }
                      pre = node;
                  }
              }
              return true;
          }
      };
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24
      • 25
      • 26
      • 27
      • 28
      • 29
      • 30
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36
    2. 对比参考给出的迭代法:

    • while(cur != NULL || !st.empty())保证:初始传入的根节点不为空。后序根据栈不为空进入循环。
    • 如果访问的不是空节点,就交给左子树。
    • 如果访问到cur是空节点,那么处理栈中记录的元素,比较判断后符合二叉搜索树继续,同时更新pre指向。把下一棒交给右子树。
    • 所以这个中序迭代的基础用的不是统一迭代模版。区别于前后序入栈的实现,单独适用于中序遍历。
      class Solution {
      public:
          bool isValidBST(TreeNode* root) {
              stack<TreeNode*> st;
              TreeNode* cur = root;
              TreeNode* pre = NULL; // 记录前一个节点
              while (cur != NULL || !st.empty()) {
                  if (cur != NULL) {
                      st.push(cur);
                      cur = cur->left;                // 左
                  } else {
                      cur = st.top();                 // 中
                      st.pop();
                      if (pre != NULL && cur->val <= pre->val)
                      return false;
                      pre = cur; //保存前一个访问的结点
      
                      cur = cur->right;               // 右
                  }
              }
              return true;
          }
      };
      
      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23

总结

【98.验证二叉搜索树】:
在这里插入图片描述
(欢迎指正,转载标明出处)

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号