LeetCode 98. 验证二叉搜索树（中）

利用二叉搜索树中序遍历结果为递增序列的特点判断该二叉树是否是二叉搜索树。

题目

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树

示例

示例 1:

1
2
3
4
5
输入:
    2
   / \
  1   3
输出: true

示例 2:

1
2
3
4
5
6
7
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false

解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

考察知识点

二叉树

核心思想

直觉
对二叉树进行一个中序遍历，中序遍历为有序递增的，就是有效二叉树。
注意判断，如果结果中有重复的，直接就不认为是二叉树了

Python版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 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) -> bool:
        # 中序遍历为递增的，就是有效二叉树
        res = self.inorderTraversal(root)
        if len(res)!=len(set(res)):  # 如果有重复的，直接就不认为是二叉树了
            return False
        tmp = res[:]
        tmp.sort()
        return res == tmp

    def inorderTraversal(self, root):
        """
        In-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        res = []
        stack = []
        node = root
        while node or len(stack) > 0:
            while node:  # 把当前节点的所有左侧子结点压入栈 
                stack.append(node)
                node = node.left
            if len(stack):  # 访问节点，处理该节点的右子树
                node = stack.pop()  # 由于之前把左子树先压入了，所以这里先弹出左子树节点
                res.append(node.val)
                node = node.right  #  然后设置新的node为右子树，下一次while循环就会去处理右子树了。这样一来就实现了左 -> 根 -> 右 的顺序。
        return res