【二叉查找树】03验证是否为二叉查找树【Validate Binary Search Tree】

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#include "BinaryTree.h"

using namespace std;


/**
 * Definition for binary tree
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
bool islessthanroot(TreeNode *left, int val)
{
    if(left == NULL)
    {
        return true;
    }
    if(left->val >= val)
    {
        return false;
    }
    return islessthanroot(left->left, val) && islessthanroot(left->right, val);
}

bool islargethanroot(TreeNode *right, int val)
{
    if(right == NULL)
    {
        return true;
    }
    if(right->val <= val)
    {
        return false;
    }
    return islargethanroot(right->left, val) && islargethanroot(right->right, val);
}

bool isValidBST(TreeNode *root)
{
    if(root == NULL)
    {
        return true;
    }
    if(islessthanroot(root->left, root->val) && islargethanroot(root->right, root->val))
    {
        return isValidBST(root->left) && isValidBST(root->right);
    }
    else
    {
        return false;
    }
}


// 树中结点含有分叉，
//                  6
//              /       \
//             2         7
//           /   \
//          1     4
//               / \
//              3   5
int main()
{
    TreeNode *pNodeA1 = CreateBinaryTreeNode(6);
    TreeNode *pNodeA2 = CreateBinaryTreeNode(2);
    TreeNode *pNodeA3 = CreateBinaryTreeNode(7);
    TreeNode *pNodeA4 = CreateBinaryTreeNode(1);
    TreeNode *pNodeA5 = CreateBinaryTreeNode(4);
    TreeNode *pNodeA6 = CreateBinaryTreeNode(3);
    TreeNode *pNodeA7 = CreateBinaryTreeNode(5);

    ConnectTreeNodes(pNodeA1, pNodeA2, pNodeA3);
    ConnectTreeNodes(pNodeA2, pNodeA4, pNodeA5);
    ConnectTreeNodes(pNodeA5, pNodeA6, pNodeA7);



    bool ans = isValidBST(pNodeA1);

    if (ans == true)
    {
        cout << "Valid BST" << endl;
    }
    else
    {
        cout << "Not Valid BST" << endl;
    }

    DestroyTree(pNodeA1);
    return 0;
}