LeetCode 练习#

Validate Binary Search Tree#

各大公司热门面试题

https://leetcode.com/problems/validate-binary-search-tree/

如何才算一个二叉搜索树？

  • 当前节点的值大于其所有的左子树节点的值

  • 当前节点的值小于其所有的右子树节点的值

  • 当前节点的左子树和右子树也是二叉搜索树

../_images/leetcode-valid-bst.PNG

常用的解题方法

  • 按二叉搜索树的定义，暴力比较

  • 按In order遍历这个树，然后对遍历结果进行检查，看是否是顺序排列

暴力解法#

基本的逻辑：

  • 如果root是None，则返回True

  • 否则就已当前节点为root根节点，找到左子树的最大值，右子树的最小值

  • 如果左子树的最大值比当前节点的值大，或者右子树的最小值比当前节点值小，返回False

  • 否则就继续查找，以当前节点的左右节点分别为根节点，进行递归检查

参考代码

 1# Definition for a binary tree node.
 2# class TreeNode:
 3#     def __init__(self, val=0, left=None, right=None):
 4#         self.val = val
 5#         self.left = left
 6#         self.right = right
 7class Solution:
 8    def isValidBST(self, root: Optional[TreeNode]) -> bool:
 9
10        if root is None:
11            return True
12        if root.left:
13            if root.val <= self.find_max(root.left):
14                return False
15        if root.right:
16            if root.val >= self.find_min(root.right):
17                return False
18
19        if self.isValidBST(root.left) and self.isValidBST(root.right):
20            return True
21        return False
22
23    def find_max(self, root):
24
25        # 最大值在右子树的最右一个节点
26        while root.right:
27            root = root.right
28        return root.val
29
30    def find_min(self, root):
31        while root.left:
32            root = root.left
33
34        return root.val

暴力解法的优化

 1# Definition for a binary tree node.
 2# class TreeNode(object):
 3#     def __init__(self, x):
 4#         self.val = x
 5#         self.left = None
 6#         self.right = None
 7
 8
 9class Solution(object):
10    def isValidBST(self, root):
11        return self.isValidBSTRecu(root, float("-inf"), float("inf"))
12
13    def isValidBSTRecu(self, root, low, high):
14        if root is None:
15            return True
16
17        return (
18            low < root.val
19            and root.val < high
20            and self.isValidBSTRecu(root.left, low, root.val)
21            and self.isValidBSTRecu(root.right, root.val, high)
22        )

DFS In Order遍历#

参考代码

 1# Definition for a binary tree node.
 2# class TreeNode:
 3#     def __init__(self, val=0, left=None, right=None):
 4#         self.val = val
 5#         self.left = left
 6#         self.right = right
 7class Solution:
 8    def dfs(self, root):
 9        # in order DFS
10        results = []
11
12        def traversal(current_node):
13            if current_node.left is not None:
14                traversal(current_node.left)
15            results.append(current_node.val)
16            if current_node.right is not None:
17                traversal(current_node.right)
18
19        traversal(root)
20        return results
21
22    def isValidBST(self, root: Optional[TreeNode]) -> bool:
23
24        results = self.dfs(root)
25
26        i = 1
27        flag = 1
28        while i < len(results):
29            if results[i] <= results[i - 1]:
30                flag = 0
31                break
32            i += 1
33        return True if flag == 1 else False

代码优化

 1# Definition for a binary tree node.
 2# class TreeNode:
 3#     def __init__(self, val=0, left=None, right=None):
 4#         self.val = val
 5#         self.left = left
 6#         self.right = right
 7class Solution:
 8    def dfs(self, root):
 9        # in order DFS
10        self.flag = 1
11        self.pre_node = None
12
13        def traversal(current_node):
14            if self.flag != 1:
15                return
16            if current_node.left is not None:
17                traversal(current_node.left)
18            # results.append(current_node.val)
19            if self.pre_node:
20                if self.pre_node.val >= current_node.val:
21                    self.flag = 0
22            self.pre_node = current_node
23
24            if current_node.right is not None:
25                traversal(current_node.right)
26
27        traversal(root)
28        return True if self.flag == 1 else False
29
30    def isValidBST(self, root: Optional[TreeNode]) -> bool:
31
32        return self.dfs(root)