题目地址
https://leetcode.com/problems/validate-binary-search-tree/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 1:
2
/ \
1 3
Input: [2,1,3]
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
思路
中序遍历
这道题是让你验证一棵树是否为二叉查找树(BST)。 由于中序遍历的性质如果一个树遍历的结果是有序数组,那么他也是一个二叉查找树(BST)
,
我们只需要中序遍历,然后两两判断是否有逆序的元素对即可,如果有,则不是BST,否则即为一个BST。
定义法
根据定义,一个结点若是在根的左子树上,那它应该小于根结点的值而大于左子树最大值;若是在根的右子树上,那它应该大于根结点的值而小于右子树最小值。也就是说,每一个结点必须落在某个取值范围:
- 根结点的取值范围为(考虑某个结点为最大或最小整数的情况):(long_min, long_max)
- 左子树的取值范围为:(current_min, root.value)
- 右子树的取值范围为:(root.value, current_max)
关键点解析
- 二叉树的基本操作(遍历)
- 中序遍历一个二叉查找树(BST)的结果是一个有序数组
- 如果一个树遍历的结果是有序数组,那么他也是一个二叉查找树(BST)
代码
中序遍历
- 语言支持:JS,C++, Java
JavaScript Code:
/* * @lc app=leetcode id=98 lang=javascript * * [98] Validate Binary Search Tree */ /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {boolean} */ var isValidBST = function(root) { if (root === null) return true; if (root.left === null && root.right === null) return true; const stack = [root]; let cur = root; let pre = null; function insertAllLefts(cur) { while(cur && cur.left) { const l = cur.left; stack.push(l); cur = l; } } insertAllLefts(cur); while(cur = stack.pop()) { if (pre && cur.val <= pre.val) return false; const r = cur.right; if (r) { stack.push(r); insertAllLefts(r); } pre = cur; } return true; };
C++ Code:
// 递归 class Solution { public: bool isValidBST(TreeNode* root) { TreeNode* prev = nullptr; return validateBstInorder(root, prev); } private: bool validateBstInorder(TreeNode* root, TreeNode*& prev) { if (root == nullptr) return true; if (!validateBstInorder(root->left, prev)) return false; if (prev != nullptr && prev->val >= root->val) return false; prev = root; return validateBstInorder(root->right, prev); } }; // 迭代 class Solution { public: bool isValidBST(TreeNode* root) { auto s = vector<TreeNode*>(); TreeNode* prev = nullptr; while (root != nullptr || !s.empty()) { while (root != nullptr) { s.push_back(root); root = root->left; } root = s.back(); s.pop_back(); if (prev != nullptr && prev->val >= root->val) return false; prev = root; root = root->right; } return true; } };
Java Implementation
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isValidBST(TreeNode root) { Stack<Integer> stack = new Stack<> (); TreeNode previous = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (previous != null && root.val <= previous.val ) return false; previous = root; root = root.right; } return true; } }
定义法
- 语言支持:C++,Python3, Java
C++ Code:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ // 递归 class Solution { public: bool isValidBST(TreeNode* root) { return helper(root, LONG_MIN, LONG_MAX); } private: bool helper(const TreeNode* root, long min, long max) { if (root == nullptr) return true; if (root->val >= max || root->val <= min) return false; return helper(root->left, min, root->val) && helper(root->right, root->val, max); } }; // 循环 class Solution { public: bool isValidBST(TreeNode* root) { if (root == nullptr) return true; auto ranges = queue<pair<long, long>>(); ranges.push(make_pair(LONG_MIN, LONG_MAX)); auto nodes = queue<const TreeNode*>(); nodes.push(root); while (!nodes.empty()) { auto sz = nodes.size(); for (auto i = 0; i < sz; ++i) { auto range = ranges.front(); ranges.pop(); auto n = nodes.front(); nodes.pop(); if (n->val >= range.second || n->val <= range.first) { return false; } if (n->left != nullptr) { ranges.push(make_pair(range.first, n->val)); nodes.push(n->left); } if (n->right != nullptr) { ranges.push(make_pair(n->val, range.second)); nodes.push(n->right); } } } return true; } };
Python Code:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isValidBST(self, root: TreeNode, area: tuple=(-float('inf'), float('inf'))) -> bool: """思路如上面的分析,用Python表达会非常直白 :param root TreeNode 节点 :param area tuple 取值区间 """ if root is None: return True is_valid_left = root.left is None or\ (root.left.val < root.val and area[0] < root.left.val < area[1]) is_valid_right = root.right is None or\ (root.right.val > root.val and area[0] < root.right.val < area[1]) # 左右节点都符合,说明本节点符合要求 is_valid = is_valid_left and is_valid_right # 递归下去 return is_valid\ and self.isValidBST(root.left, (area[0], root.val))\ and self.isValidBST(root.right, (root.val, area[1]))
Java Code:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isValidBST(TreeNode root) { return helper(root, null, null); } private boolean helper(TreeNode root, Integer lower, Integer higher) { if (root == null) return true; if (lower != null && root.val <= lower) return false; if (higher != null && root.val >= higher) return false; if (!helper(root.left, lower, root.val)) return false; if (!helper(root.right, root.val, higher)) return false; return true; } }
相关题目
230.kth-smallest-element-in-a-bst
LeetCode题解501.Find-Mode-in-Binary-Search-TreeProblem on Leetcode https://leetcode.com/problems/find-mode-in-binary-search-tree/ Description Given a binary search tree (BST) with duplicates, find all the mode(s) (the most freq…
LeetCode题解96.unique-binary-search-trees题目地址(96. 不同的二叉搜索树) https://leetcode-cn.com/problems/unique-binary-search-trees-ii/description/ 题目描述 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二…
LeetCode题解95.unique-binary-search-trees-ii题目地址(95. 不同的二叉搜索树 II) https://leetcode-cn.com/problems/unique-binary-search-trees-ii/description/ 题目描述 给定一个整数 n,生成所有由 1 ... n 为节点所组成的二叉搜索树。 示例: 输入: 3 输出: [ [1,null,3,2], [3,2,n…
LeetCode题解94.binary-tree-inorder-traversal题目地址 https://leetcode.com/problems/binary-tree-inorder-traversal/description/ 题目描述 Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2…
LeetCode题解124.binary-tree-maximum-path-sum题目地址 https://leetcode.com/problems/binary-tree-maximum-path-sum/description/ 题目描述 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as a…