98. 验证二叉搜索树
给你一个二叉树的根节点 root
,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
![](https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg)
输入:root = [2,1,3] 输出:true
示例 2:
![](https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg)
输入:root = [5,1,4,null,null,3,6] 输出:false 解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
- 树中节点数目范围在
[1, 104]
内 -231 <= Node.val <= 231 - 1
解析:
为啥通过率这么低?
看看中序遍历是否是递增序列就可以
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void dfs(TreeNode* root, vector<int>& node) { if(root == nullptr) return; dfs(root->left, node); node.push_back(root->val); dfs(root->right, node); } bool isValidBST(TreeNode* root) { vector<int> node; dfs(root, node); bool flag = 0; for(int i = 1; i < node.size(); i++) { if(node[i] <= node[i - 1]) { flag = 1; break; } } return !flag; } };
标签:node,right,TreeNode,验证,二叉,98,root,节点,left From: https://www.cnblogs.com/WTSRUVF/p/16625895.html