【leetcode】验证二叉搜索树

题目:

给定一个二叉树,判断其是否是一个有效的二叉搜索树(Binary Search Tree, BST)。

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

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

示例:
输入: [2 1 3]
2
/
1 3
输出: true

输入:[5,1,4,null,null,3,6]
5
/
1 4
/
3 6
输出: false

分析:

程序

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
100
101
102
#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BinaryTree
{
public:
BinaryTree() : root(nullptr) {}
TreeNode* createTree(string input);
bool isValidBST();
private:
TreeNode *root;
void trimSpaces(string &input) {
input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
return !isspace(ch);
}));
input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
return !isspace(ch);
}).base(), input.end());
}
};

TreeNode* BinaryTree::createTree(string input) {
trimSpaces(input);
input = input.substr(1, input.length() - 2);
if (!input.size())
return nullptr;

string item;
stringstream ss;
ss.str(input);
getline(ss, item, ',');

TreeNode* root = new TreeNode(stoi(item));
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);

while (true) {
TreeNode* node = nodeQueue.front();
nodeQueue.pop();

if (!getline(ss, item, ','))
break;

trimSpaces(item);
if (item != "null") {
node->left = new TreeNode(stoi(item));
nodeQueue.push(node->left);
}

if (!getline(ss, item, ','))
break;

trimSpaces(item);
if (item != "null") {
node->right = new TreeNode(stoi(item));
nodeQueue.push(node->right);
}
}
return root;
}

bool BinaryTree::isValidBST() {
stack<TreeNode*> stack;
long long predt = (long long)INT_MIN - 1;

while (!stack.empty() || root != nullptr) {
while (root != nullptr) {
stack.push(root);
root = root->left;
}
root = stack.top();
stack.pop();
if (root->val <= predt)
return false;
predt = root->val;
root = root->right;
}
return true;
}

int main() {
string line;
while (getline(cin, line)) {
BinaryTree tree = BinaryTree();
tree.createTree(line);
cout << tree.isValidBST() << endl;
}
return 0;
}

SQL基础教程

《SQL基础教程(第2版)》读书笔记

【Princeton】算法(3):排序

排序(sort)是将一组对象按照某种74em逻辑顺序重新排列的过程,现实生活中我们经常需要对各种东西进行排序,在计算机上处理各种数据时也不例外。

这里介绍几种初级排序算法以及两种经典排序算法——归并排序、快速排序。

【Princeton】算法(2):栈和队列

这里介绍一些数据结构相关的基本概念以及两种最基本的数据结构–栈和队列。

【Princeton】算法(1):Union-Find

在计算机科学(CS)中,算法(Algorithm)是描述一种有限、确定、有效,并且适合用计算机语言来实现的解决问题的方法,它是CS领域的基础与核心。

这里先通过一个动态连通性问题,来了解设计、分析算法的基本过程。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×