leetcode dfs Validate Binary Search Tree
LeetCode Tree search Binary DFS validate
2023-09-14 09:08:11 时间
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.
题意：给定一棵二叉树，推断它是不是合法的二叉查找树
思路：dfs
合法二叉查找树必须满足下面两个条件
1.左子树和右子树都是合法二叉查找树
2.左子树的最右叶子节点 < 根 < 右子树的最左叶子节点
复杂度：时间O(n)，空间O(log n)
bool isValidBST(TreeNode *root) {
if(!root) return true;
TreeNode *right_most = root->left, *left_most = root->right;
while(right_most && right_most->right){
right_most = right_most->right;
}
while(left_most && left_most->left){
left_most = left_most->left;
}
return isValidBST(root->left) && isValidBST(root->right)
&& (!right_most || right_most->val < root->val)
&& (!left_most || root->val < left_most->val);
}
相关文章
- Java实现 LeetCode 773 滑动谜题（BFS）
- Java实现 LeetCode 215. 数组中的第K个最大元素
- Java实现 LeetCode 160 相交链表
- Java实现 LeetCode 82 删除排序链表中的重复元素 II（二）
- Java实现LeetCode 111. Minimum Depth of Binary Tree
- LeetCode：111_Minimum Depth of Binary Tree | 二叉树的最小深度 | Easy
- [LeetCode] Invert Binary Tree
- 【二叉树】LeetCode 101. 对称二叉树【简单】
- LeetCode（77）：组合
- LeetCode-744. 寻找比目标字母大的最小字母【二分查找】
- leetcode--Recover Binary Search Tree
- [LeetCode] 108. Convert Sorted Array to Binary Search Tree ☆(升序数组转换成一个平衡二叉树)
- [LeetCode] 110. Balanced Binary Tree ☆(二叉树是否平衡)
- leetcode - Symmetric Tree
- [LeetCode] Flatten Binary Tree to Linked List
- [Leetcode]-Same Tree
- leetcode 572. Subtree of Another Tree
- leetcode 107. Binary Tree Level Order Traversal II
- leetcode 669. Trim a Binary Search Tree
- 【LeetCode】合并二叉树