C++實(shí)現(xiàn)LeetCode(98.驗(yàn)證二叉搜索樹)
[LeetCode] 98. Validate Binary Search Tree 驗(yàn)證二叉搜索樹
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 1:
Input:
2
/ \
1 3
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
這道驗(yàn)證二叉搜索樹有很多種解法，可以利用它本身的性質(zhì)來做，即左<根<右，也可以通過利用中序遍歷結(jié)果為有序數(shù)列來做，下面我們先來看最簡單的一種，就是利用其本身性質(zhì)來做，初始化時(shí)帶入系統(tǒng)最大值和最小值，在遞歸過程中換成它們自己的節(jié)點(diǎn)值，用long代替int就是為了包括int的邊界條件，代碼如下：
C++ 解法一：
// Recursion without inorder traversal
class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, LONG_MIN, LONG_MAX);
}
bool isValidBST(TreeNode* root, long mn, long mx) {
if (!root) return true;
if (root->val <= mn || root->val >= mx) return false;
return isValidBST(root->left, mn, root->val) && isValidBST(root->right, root->val, mx);
}
};
Java 解法一：
public class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean valid(TreeNode root, long low, long high) {
if (root == null) return true;
if (root.val <= low || root.val >= high) return false;
return valid(root.left, low, root.val) && valid(root.right, root.val, high);
}
}
這題實(shí)際上簡化了難度，因?yàn)橛械臅r(shí)候題目中的二叉搜索樹會(huì)定義為左<=根<右，而這道題設(shè)定為一般情況左<根<右，那么就可以用中序遍歷來做。因?yàn)槿绻蝗サ糇?根這個(gè)條件的話，那么下邊兩個(gè)數(shù)用中序遍歷無法區(qū)分：
20 20
/ \
20 20
它們的中序遍歷結(jié)果都一樣，但是左邊的是 BST，右邊的不是 BST。去掉等號(hào)的條件則相當(dāng)于去掉了這種限制條件。下面來看使用中序遍歷來做，這種方法思路很直接，通過中序遍歷將所有的節(jié)點(diǎn)值存到一個(gè)數(shù)組里，然后再來判斷這個(gè)數(shù)組是不是有序的，代碼如下：
C++ 解法二：
// Recursion
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
vector<int> vals;
inorder(root, vals);
for (int i = 0; i < vals.size() - 1; ++i) {
if (vals[i] >= vals[i + 1]) return false;
}
return true;
}
void inorder(TreeNode* root, vector<int>& vals) {
if (!root) return;
inorder(root->left, vals);
vals.push_back(root->val);
inorder(root->right, vals);
}
};
Java 解法二：
public class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
inorder(root, list);
for (int i = 0; i < list.size() - 1; ++i) {
if (list.get(i) >= list.get(i + 1)) return false;
}
return true;
}
public void inorder(TreeNode node, List<Integer> list) {
if (node == null) return;
inorder(node.left, list);
list.add(node.val);
inorder(node.right, list);
}
}
下面這種解法跟上面那個(gè)很類似，都是用遞歸的中序遍歷，但不同之處是不將遍歷結(jié)果存入一個(gè)數(shù)組遍歷完成再比較，而是每當(dāng)遍歷到一個(gè)新節(jié)點(diǎn)時(shí)和其上一個(gè)節(jié)點(diǎn)比較，如果不大于上一個(gè)節(jié)點(diǎn)那么則返回 false，全部遍歷完成后返回 true。代碼如下：
C++ 解法三：
class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode *pre = NULL;
return inorder(root, pre);
}
bool inorder(TreeNode* node, TreeNode*& pre) {
if (!node) return true;
bool res = inorder(node->left, pre);
if (!res) return false;
if (pre) {
if (node->val <= pre->val) return false;
}
pre = node;
return inorder(node->right, pre);
}
};
當(dāng)然這道題也可以用非遞歸來做，需要用到棧，因?yàn)橹行虮闅v可以非遞歸來實(shí)現(xiàn)，所以只要在其上面稍加改動(dòng)便可，代碼如下：
C++ 解法四：
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> s;
TreeNode *p = root, *pre = NULL;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
if (pre && p->val <= pre->val) return false;
pre = p;
p = p->right;
}
return true;
}
};
Java 解法四：
public class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> s = new Stack<TreeNode>();
TreeNode p = root, pre = null;
while (p != null || !s.empty()) {
while (p != null) {
s.push(p);
p = p.left;
}
p = s.pop();
if (pre != null && p.val <= pre.val) return false;
pre = p;
p = p.right;
}
return true;
}
}
最后還有一種方法，由于中序遍歷還有非遞歸且無棧的實(shí)現(xiàn)方法，稱之為 Morris 遍歷，可以參考博主之前的博客 Binary Tree Inorder Traversal，這種實(shí)現(xiàn)方法雖然寫起來比遞歸版本要復(fù)雜的多，但是好處在于是 O(1) 空間復(fù)雜度，參見代碼如下：
C++ 解法五:
class Solution {
public:
bool isValidBST(TreeNode *root) {
if (!root) return true;
TreeNode *cur = root, *pre, *parent = NULL;
bool res = true;
while (cur) {
if (!cur->left) {
if (parent && parent->val >= cur->val) res = false;
parent = cur;
cur = cur->right;
} else {
pre = cur->left;
while (pre->right && pre->right != cur) pre = pre->right;
if (!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = NULL;
if (parent->val >= cur->val) res = false;
parent = cur;
cur = cur->right;
}
}
}
return res;
}
};
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(98.驗(yàn)證二叉搜索樹)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)驗(yàn)證二叉搜索樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- C++數(shù)據(jù)結(jié)構(gòu)二叉搜索樹的實(shí)現(xiàn)應(yīng)用與分析
- C++實(shí)現(xiàn)LeetCode(173.二叉搜索樹迭代器)
- C++實(shí)現(xiàn)LeetCode(109.將有序鏈表轉(zhuǎn)為二叉搜索樹)
- C++實(shí)現(xiàn)LeetCode(108.將有序數(shù)組轉(zhuǎn)為二叉搜索樹)
- C++實(shí)現(xiàn)LeetCode(99.復(fù)原二叉搜索樹)
- C++實(shí)現(xiàn)LeetCode(96.獨(dú)一無二的二叉搜索樹)
- C++實(shí)現(xiàn)LeetCode(95.獨(dú)一無二的二叉搜索樹之二)
- C++ 二叉搜索樹(BST)的實(shí)現(xiàn)方法
- C++ 超詳細(xì)快速掌握二叉搜索樹
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C語言版三子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
本文介紹了如何使用C++語言處理位圖圖像，包括讀取、修改、保存等操作。通過具體的代碼示例，讀者可以學(xué)習(xí)到如何利用C++中的位運(yùn)算、數(shù)組和文件操作等知識(shí)點(diǎn)完成位圖處理任務(wù)。同時(shí)，本文也提供了一些常用的圖像處理算法供讀者參考，幫助讀者更好地理解位圖處理過程2023-04-04
C語言編程中的聯(lián)合體union入門學(xué)習(xí)教程
這篇文章主要介紹了C語言編程中的聯(lián)合體union入門學(xué)習(xí)教程,也是C語言入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-12-12
基于c++的中國象棋游戲設(shè)計(jì)與實(shí)現(xiàn)
C++中HTTP?代理服務(wù)器的設(shè)計(jì)與實(shí)現(xiàn)詳解
Qt數(shù)據(jù)庫應(yīng)用之超級(jí)自定義委托