-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path98-IsValidBST.h
More file actions
84 lines (67 loc) · 1.2 KB
/
98-IsValidBST.h
File metadata and controls
84 lines (67 loc) · 1.2 KB
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
#pragma once
#include <iostream>
#include <vector>
using namespace std;
/*
给定一个二叉树的头结点head,已知其中没有重复值的节点，判断二叉树是否为搜索二叉树
*/
//Definition for a binary tree node.
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
void Test98();
bool isValidBST(TreeNode* pRootNode);
protected:
private:
};
void Solution::Test98()
{
}
bool Solution::isValidBST(TreeNode* pRootNode)
{
if (nullptr == pRootNode)
{
return true;
}
bool bRet = true;
TreeNode* pPre = nullptr;
TreeNode* pNode = pRootNode;
TreeNode* pCur = nullptr;
while (pNode != nullptr)
{
pCur = pNode->left;
if (pCur != nullptr)
{
while (pCur->right != nullptr && pCur->right != pNode)
{
pCur = pCur->right;
}
//
if (pCur->right == nullptr)
{
pCur->right = pNode;
pNode = pNode->left;
continue;
}
else
{
pCur->right = nullptr;
}
}
//有重复值节点
// if (pPre != nullptr && pPre->_value >= pNode->_value)
if (pPre != nullptr && pPre->val > pNode->val)
{
bRet = false;
}
pPre = pNode;
pNode = pNode->right;
}
return bRet;
}