-
Notifications
You must be signed in to change notification settings - Fork 1
/
trees.py
73 lines (67 loc) · 1.97 KB
/
trees.py
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# recursive valid BST
class Solution(object):
def isValidBST(self, root, lessThan = float('inf'), largerThan = float('-inf')):
if not root:
return True
if root.val <= largerThan or root.val >= lessThan:
return False
return self.isValidBST(root.left, min(lessThan, root.val), largerThan) and \
self.isValidBST(root.right, lessThan, max(root.val, largerThan))
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
st = deque()
pre = None
while root != null or stack:
while root != null:
st.append(root)
root = root.left
# stack method (can be applied to other problems)
class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
st = deque()
pre = None
while root or st:
while root:
st.append(root)
root = root.left
root = st.pop()
if pre and root.val <= pre.val:
return False
pre = root
root = root.right
return True
# check if tree t is a subtree of s
def isSubtree(s, t):
if not s: return False
if isSame(s,t): return True
return isSubtree(s.left, t) or isSubtree(s.right, t)
def isSame(s, t):
if not s and not t:
return True
if not s or not t:
return False
return s.val == t.val and isSame(s.left, t.left) and isSame(s.right, t.right)