[LeetCode] Medium - 98. Validate Binary Search Tree (G,M,A,F) *

Source From Here
Question
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:

view plaincopy to clipboardprint?

1.   2  
2. / \  
3. 1   3  

Input: [2,1,3]
Output: true

Example 2:

view plaincopy to clipboardprint?

1.   5  
2. / \  
3. 1   4  
4.    / \  
5.   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.

Solution

Naive

view plaincopy to clipboardprint?

1. # Definition for a binary tree node.  
2. class TreeNode:  
3.     def __init__(self, x):  
4.         self.val = x  
5.         self.left = None  
6.         self.right = None  
7.   
8.   
9. class Solution:  
10.     def isValidBST(self, root):  
11.         if not root:  
12.             return True  
13.   
14.         inf = float('inf')  
15.         queue = [(root, inf, -inf)]  
16.         while queue:  
17.             n, max_v, min_v = queue.pop(0)  
18.             print("N={}; max={}; min={}".format(n.val, max_v, min_v))  
19.             if n.val >= max_v or n.val <= min_v:  
20.                 return False  
21.   
22.             if n.left:  
23.                 if n.left.val >= n.val:  
24.                     return False  
25.   
26.                 queue.append((n.left, min(max_v, n.val), min_v))  
27.             if n.right:  
28.                 if n.right.val <= n.val:  
29.                     return False  
30.   
31.                 queue.append((n.right, max_v, max(min_v, n.val)))  
32.   
33.         return True  
34.   
35. def build_t(elements):  
36.     datas = []  
37.     datas.extend(elements)  
38.     root = TreeNode(datas.pop(0))  
39.     queue = [root]  
40.     while queue and datas:  
41.         n = queue.pop(0)  
42.         v1 = datas.pop(0)  
43.         v2 = datas.pop(0)  
44.   
45.         if v1 is not None:  
46.             n.left = TreeNode(v1)  
47.             queue.append(n.left)  
48.   
49.         if v2 is not None:  
50.             n.right = TreeNode(v2)  
51.             queue.append(n.right)  
52.   
53.     return root  
54.   
55.   
56. if __name__ == '__main__':  
57.     s = Solution()  
58.     for datas, ans in [  
59.                         ([2, 1, 3], True),  
60.                         ([5, 1, 4, None, None, 3, 6], False),  
61.                         ([10, 5, 15, None, None, 6, 20], False),  
62.                         ([10, 5, 15, None, None, 14, 20], True),  
63.                         ([3, 1, 5, 0, 2, 4, 6, None, None, None, 3], False)  
64.                       ]:  
65.         root = build_t(datas)  
66.         rel = s.isValidBST(root)  
67.         print("{}: {}".format(datas, rel))  
68.         assert ans == rel  

Runtime: 44 ms, faster than 62.41% of Python3 online submissions for Validate Binary Search Tree.
Memory Usage: 16.1 MB, less than 22.99% of Python3 online submissions for Validate Binary Search Tree.

Golden (link)

view plaincopy to clipboardprint?

1. class Solution:  
2.     def isValidBST(self, root):  
3.         """  
4.         :type root: TreeNode  
5.         :rtype: bool  
6.         """  
7.         def helper(node, lower = float('-inf'), upper = float('inf')):  
8.             if not node:  
9.                 return True  
10.               
11.             val = node.val  
12.             if val <= lower or val >= upper:  
13.                 return False  
14.   
15.             if not helper(node.right, val, upper):  
16.                 return False  
17.             if not helper(node.left, lower, val):  
18.                 return False  
19.             return True  
20.   
21.         return helper(root)  

Runtime: 48 ms, faster than 28.12% of Python3 online submissions for Validate Binary Search Tree.
Memory Usage: 16.1 MB, less than 24.14% of Python3 online submissions for Validate Binary Search Tree.

Supplement
* 【LeetCode】98. Validate Binary Search Tree 解题报告（Python ＆ C++ & Java）
* Youtube - LeetCode 98. Validate Binary Search Tree...rithm Explained) by Nick White