Validate Binary Search Tree 题解
原创文章,拒绝转载
题目来源:https://leetcode.com/problems/validate-binary-search-tree/description/
Description
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example
Example 1:
2
/
1 3
Binary tree [2,1,3]
, return true.
Example 2:
1
/
2 3
Binary tree [1,2,3]
, return false.
Solution
class Solution {
private:
void inOrder(TreeNode* node, vector<int>& arr) {
if (node != NULL) {
inOrder(node -> left, arr);
arr.push_back(node -> val);
inOrder(node -> right, arr);
}
}
public:
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
vector<int> inOrderArr;
inOrder(root, inOrderArr);
int i;
int size = inOrderArr.size();
for (i = 0; i < size - 1; i++) {
if (inOrderArr[i] >= inOrderArr[i + 1])
return false;
}
return true;
}
};
解题描述
这道题题意是要检查给出的一棵二叉树是不是一棵BST。上面给出的是一开始的解法,对二叉树进行中序遍历之后记录节点值在一个数组中。遍历结束后检查数组是不是单调递增。但是这种做法不仅使用了递归,会增加运行开销,而且还需要重新遍历一次节点值数组,总的来说用了2趟。
下面给出的是迭代方式(使用栈模拟递归)中序遍历,并且在遍历的过程中增加对BST的判断,少了一趟遍历。
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
stack<TreeNode*> nodeStack;
TreeNode* preNode = NULL;
while (root || !nodeStack.empty()) {
while (root) {
nodeStack.push(root);
root = root -> left;
}
root = nodeStack.top();
nodeStack.pop();
if (preNode != NULL && preNode -> val >= root -> val)
return false;
preNode = root;
root = root -> right;
}
return true;
}
};