题目
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入: 2 / \ 1 3 输出: true
示例 2:
输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。
解题
方法一：中序遍历(i)
因为二叉搜索树的中序遍历正好是严格递增排序，因此只要判断结果是严格递增排序的就行了。
python写法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isValidBST(self, root: TreeNode) -> bool: if not root: return True stack = [] res = [] cur = root while stack or cur: while cur: stack.append(cur) cur = cur.left cur = stack.pop() res.append(cur.val) cur = cur.right # return res==list(sorted(set(res))) i=1 while i<len(res): if res[i-1]>=res[i]: return False i+=1 return True
其中注释的那行，可以替换下面的部分。
c++写法
直接每次遍历中的节点的值 和 数组中最后一个值比较就行了。
class Solution { public: bool isValidBST(TreeNode* root) { int num; TreeNode* cur=root; stack<TreeNode*> stack; while(!stack.empty()||cur){ while(cur){ stack.push(cur); cur=cur->left; } cur=stack.top(); stack.pop(); if(!res.empty()&&cur->val<=res.back()) return false; res.push_back(cur->val); cur=cur->right; } return true; } };
