[LeetCode] Validate Binary Search Tree
LeetCode Tree search Binary validate
2023-09-11 14:17:25 时间
方法一:若是bst,中序便利后一定是有序,递增的。可以中序遍历后查看是否递增来判断
1 class Solution { 2 public: 3 bool isValidBST(TreeNode *root) { 4 5 if(root == NULL) 6 return true; 7 vector<int> result; 8 stack<TreeNode*> st; 9 10 TreeNode* p = root; 11 12 // inorder traverse 13 while(p != NULL || st.size() != 0) 14 { 15 while(p != NULL) 16 { 17 st.push(p); 18 p = p->left; 19 } 20 21 if(!st.empty()) 22 { 23 p = st.top(); 24 st.pop(); 25 result.push_back(p->val); 26 p = p->right; 27 } 28 } 29 30 //check if it is ascend 31 for(int i = 0; i < result.size()-1; i++) 32 { 33 if(result[i] < result[i+1]) 34 ; 35 else 36 return false; 37 } 38 return true; 39 40 } 41 };
方法二:使用递归,判断当前节点的值,是否在上边界和下边界之间,对于根节点,就是没有边界。然后递归判断
1 class Solution { 2 public: 3 bool isValidBST(TreeNode *root) { 4 return isValidBST(root, INT_MIN, INT_MAX); 5 } 6 bool isValidBST(TreeNode *root, int min, int max) 7 { 8 if(root == NULL) return true; 9 10 if( (root->val < max) && (root->val > min) && 11 isValidBST(root->left, min, root->val) && 12 isValidBST(root->right, root->val, max) 13 ) 14 return true; 15 else 16 return false; 17 } 18 };
方法3: 方法二没有Ac,由于两个INT_MIN出现时,所以考虑用long long 代替int即可
class Solution { public: bool isValidBST(TreeNode *root) { return isValidBST(root, (long long)INT_MIN - 1, (long long)INT_MAX + 1); } bool isValidBST(TreeNode *root, long long min, long long max) { if(root == NULL) return true; if( (root->val < max ) && (root->val > min) && isValidBST(root->left, min, root->val) && isValidBST(root->right, root->val, max) ) return true; else return false; } };
相关文章
- [LeetCode] Binary Tree Level Order Traversal 二叉树层次遍历(DFS | BFS)
- Leetcode 之Validate Binary Search Tree(53)
- Leetcode 之Construct Binary Tree(52)
- Leetcode 之Same Tree(48)
- Java实现 LeetCode 260 只出现一次的数字 III(三)
- LeetCode(78):子集
- LeetCode(57):插入区间
- LeetCode: 106_Construct Binary Tree from Inorder and Postorder Traversal | 根据中序和后序遍历构建二叉树 | Medium
- LeetCode:105_Construct Binary Tree from Preorder and Inorder Traversal | 根据前序和中序遍历构建二叉树 | Medium
- LeetCode:104_Maximum Depth of Binary Tree | 二叉树的最大深度 | Easy
- LeetCode:145_Binary Tree Postorder Traversal | 二叉树后序遍历 | Hard
- [LeetCode] Intersection of Two Arrays
- [LeetCode] Binary Tree Right Side View
- Leetcode 888. 公平的糖果交换(可以,终于解决)
- LeetCode之Balanced Binary Tree 平衡二叉树
- leetcode dfs Flatten Binary Tree to Linked List
- LeetCode 235: Lowest Common Ancestor of a Binary Search Tree
- [Leetcode]-Same Tree
- leetcode 107. Binary Tree Level Order Traversal II
- leetcode 690. Employee Importance——本质上就是tree的DFS和BFS
- leetcode 104. Maximum Depth of Binary Tree
- 【Leetcode刷题Python】106.相交链表
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【LeetCode】13.罗马数字转整数
- 【66】加一【LeetCode】