原題
給定一個(gè)二叉樹(shù)泼诱,判斷它是否是合法的二叉查找樹(shù)(BST)
一棵BST定義為:
節(jié)點(diǎn)的左子樹(shù)中的值要嚴(yán)格小于該節(jié)點(diǎn)的值倔丈。
節(jié)點(diǎn)的右子樹(shù)中的值要嚴(yán)格大于該節(jié)點(diǎn)的值沐飘。
左右子樹(shù)也必須是二叉查找樹(shù)猛拴。
一個(gè)例子:
1
/ \
2 3
/
4
\
5
上述這棵二叉樹(shù)序列化為"{1,2,3,#,#,4,#,#,5}".
解題思路
- BST的中序遍歷結(jié)果是一個(gè)升序序列
所以可以轉(zhuǎn)化為數(shù)組色迂,再遍歷一遍數(shù)組瘟忱,看是否升序奥额。時(shí)間空間復(fù)雜度都是O(n) - divide & conquer
- result每次返回一個(gè)區(qū)間的最大,最小
- conquer的時(shí)候判斷左子樹(shù)
- 遞歸判斷
min < left.val < node.val < right.val < max
完整代碼
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# 方法一
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
res = []
self.inOrderToArray(root, res)
for i in range(1, len(res)):
if res[i-1] >= res[i]:
return False
return True
def inOrderToArray(self, node, array):
if node:
if node.left:
self.inOrderToArray(node.left, array)
array.append(node.val)
if node.right:
self.inOrderToArray(node.right, array)
# 方法二
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
res, _, _ = self.Helper(root)
return res
def Helper(self, root):
if not root:
return True, - sys.maxint, sys.maxint
left = self.Helper(root.left)
right = self.Helper(root.right)
if not left[0] or not right[0]:
return False, 0, 0
if (root.left != None and left[1] >= root.val) or (root.right != None and right[2] <= root.val):
return False, 0, 0
return True, max(root.val, right[1]), min(root.val, left[2])
# 方法三
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
return self.helper(root)
def helper(self, root, min=-float("inf"), max=float("inf")):
if root is None:
return True
elif root.left == None and root.right == None:
return root.val > min and root.val < max
elif root.left == None:
return self.helper(root.right, root.val, max) and root.val > min
elif root.right == None:
return self.helper(root.left, min, root.val) and root.val < max
return self.helper(root.left, min, root.val) and self.helper(root.right, root.val, max)