98. Validate Binary Search Tree
https://leetcode.com/problems/validate-binary-search-tree/description/
这道题就是判断一个树是不是二叉查找树。二分查找树是非常常见的一种数据结构，因为它可以在O(logn)时间内实现搜索。这里我们介绍两种方法来解决这个问题。
第一种是利用二叉查找树的中序遍历有序的性质，只要对树进行一次中序遍历，而其中的结点都满足有序即可，实现上就是维护一个前驱结点，每次判断前驱结点比当前结点要小。
代码如下：
# 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):
"""
:type root: TreeNode
:rtype: bool
"""
self.pre = None
return self.helper(root)
def helper(self, root):
if not root:
return True
left = self.helper(root.left)
if self.pre and self.pre.val >= root.val:
return False
self.pre = root
return left and self.helper(root.right)
第二种方法是分支定界法，根据二叉查找树的定义来实现，其实就是对于每个结点保存左右界，保证结点满足它的左子树的每个结点比当前结点值小，右子树的每个结点比当前结点值大，实现上就是对于每个结点保存左右界，然后进行递归判断左右界不会违背即可。
代码如下：
# 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
"""
return self.helper(root, float('-inf'), float('inf'))
def helper(self, root, min_value, max_value):
if not root:
return True
if root.val <= min_value or root.val >= max_value:
return False
return self.helper(root.left, min_value, root.val) and self.helper(root.right, root.val, max_value)
上述两种方法本质上都是做一次树的遍历，所以时间复杂度是O(n)，空间复杂度是O(logn)。
99. Recover Binary Search Tree
https://leetcode.com/problems/recover-binary-search-tree/description/
这道题目还是利用二叉查找树的主要性质，就是中序遍历有序性。那么如果其中有元素被调换了，意味着中序遍历中必然出现违背有序的情况。主要考虑到就是出现违背的次数问题。这里有两种情况：
（1）如果是中序遍历相邻的两个元素被调换了，很容易想到就只需会出现一次违反情况，只需要把这个两个节点记录下来最后调换值就可以；
（2）如果是不相邻的两个元素被调换了，会发生两次逆序的情况，那么这时候需要调换的元素应该是第一次逆序前面的元素，和第二次逆序后面的元素。
算法只需要一次中序遍历，所以时间复杂度是O(n)，空间是栈大小O(logn)。
代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
self.first = self.second = None
self.pre = None
self.helper(root)
self.first.val, self.second.val = self.second.val, self.first.val
def helper(self, root):
if not root:
return
self.helper(root.left)
if self.pre and self.pre.val >= root.val:
if self.first:
self.second = root
else:
self.first = self.pre
self.second = root
self.pre = root
self.helper(root.right)
701. Insert into a Binary Search Tree
https://leetcode.com/problems/insert-into-a-binary-search-tree/description/
递归方法：root == null说明找到插入点，直接返回node；根据node.val和root.val之间的关系，选择连接在左面还是右面；为找到null结点前，返回root，不影响原始结构。
代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def insertIntoBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
if not root:
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
if val > root.val:
root.right = self.insertIntoBST(root.right, val)
return root
非递归方法：首先找到合适插入位置的父结点pre，然后根据node.val和pre.val之间的关系，将结点插入到合适的位置即可。
代码如下：
# 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 insertIntoBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
if not root:
return TreeNode(val)
pre = None
cur = root
while cur:
pre = cur
if val < cur.val:
cur = cur.left
else:
cur = cur.right
if pre:
if val < pre.val:
pre.left = TreeNode(val)
else:
pre.right = TreeNode(val)
return root
700. Search in a Binary Search Tree
https://leetcode.com/problems/search-in-a-binary-search-tree/description/
不再赘述。
代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def searchBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
if not root:
return None
if val < root.val:
return self.searchBST(root.left, val)
if val > root.val:
return self.searchBST(root.right, val)
return root
Lint11. Search Range in Binary Search Tree
https://www.lintcode.com/problem/search-range-in-binary-search-tree/description
该题很简单，递归即可。两个判断可提高效率。
代码如下：
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: param root: The root of the binary search tree
@param k1: An integer
@param k2: An integer
@return: return: Return all keys that k1<=key<=k2 in ascending order
"""
def searchRange(self, root, k1, k2):
# write your code here
result = []
if k1 > k2:
return result
self.helper(root, k1, k2, result)
return result
def helper(self, root, k1, k2, result):
if not root:
return
if root.val > k1:
self.helper(root.left, k1, k2, result)
if k1 <= root.val <= k2:
result.append(root.val)
if root.val < k2:
self.helper(root.right, k1, k2, result)
网友评论