98.验证二叉搜索树

发表于 | 分类于
字数统计: 309 | 阅读时长 ≈ 1

一、题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

示例 1:

1
2
3
4
5
输入:
    2
   / \
  1   3
输出: true

示例 2:

1
2
3
4
5
6
7
8
9
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

二、题解

1.中序遍历（非递归）

  • 使用中序遍历二叉树
  • 用一个变量记录最小值
  • 当指针p所指的值大于最小值时，更新最小值，否则返回false；

2.代码

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

#define maxSize 1000
bool isValidBST(struct TreeNode *root)
{

    struct TreeNode *stack[maxSize], *p = root;
    int top = -1;
    //flag是为了处理 -2147483648
    int a = -__INT_MAX__ - 1, flag = 0;
    while (top != -1 || p != NULL)
    {
        while (p != NULL)
        {
            stack[++top] = p;
            p = p->left;
        }
        p = stack[top--];
        if (p->val > a || flag == 0)
        {
            a = p->val;
            flag = 1;
        }
        else
            return false;
        p = p->right;
    }
    return true;
}