BST
切记，基本所有与BST有关的题目，都要用到一个BST的性质，那就是BST中序遍历有序性。
96. Unique Binary Search Trees
https://leetcode.com/problems/unique-binary-search-trees/description/
其实这是一道动态规划的题目，放在这只是保证BST题目的完整性。
这道题要求可行的二叉查找树的数量，其实二叉查找树可以任意取根，只要满足中序遍历有序的要求就可以。从处理子问题的角度来看，选取一个结点为根，就把结点切成左右子树，以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积，所以总的数量是将以所有结点为根的可行结果累加起来。
由于这道题符合卡特兰常数的模型，所以直接使用动态规划计算该卡特兰常数即可，计算时注意下标的Corner Case。
时间上每次求解i个结点的二叉查找树数量的需要一个i步的循环，总体要求n次，所以总时间复杂度是O(1+2+...+n)=O(n^2)。空间上需要一个数组来维护，并且需要前i个的所有信息，所以是O(n)。
DP Solution in 6 lines with explanation. F(i, n) = G(i-1) * G(n-i)
代码如下：
class Solution:
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
for i in range(2, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[n]
95. Unique Binary Search Trees II
https://leetcode.com/problems/unique-binary-search-trees-ii/description/
这道题是求解所有可行的二叉查找树，从Unique Binary Search Trees中我们已经知道，可行的二叉查找树的数量是相应的卡特兰数，不是一个多项式时间的数量级，所以我们要求解所有的树，自然是不能多项式时间内完成的了。算法上还是用求解NP问题的方法来求解，也就是N-Queens中介绍的在循环中调用递归函数求解子问题。思路是每次一次选取一个结点为根，然后递归求解左右子树的所有结果，最后根据左右子树的返回的所有子树，依次选取然后接上（每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共有左右子树数量的乘积种情况），构造好之后作为当前树的结果返回。
代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0:
return []
return self.helper(1, n)
def helper(self, start, end):
result = []
if start > end:
result.append(None)
return result
for i in range(start, end + 1):
left = self.helper(start, i - 1)
right = self.helper(i + 1, end)
for l in left:
for r in right:
root = TreeNode(i)
root.left = l
root.right = r
result.append(root)
return result
108. Convert Sorted Array to Binary Search Tree
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
从本质来看，如果把一个数组看成一棵树（也就是以中点为根，左右为左右子树，依次下去）数组就等价于一个二分查找树。所以如果要构造这棵树，那就是把中间元素转化为根，然后递归构造左右子树。递归的写法跟常规稍有不同，就是要把根root先new出来，然后它的左节点接到递归左边部分的返回值，右节点接到递归右边部分的返回值，最后将root返回回去。这个模板在树的构造中非常有用，其他几道题也都是按照这个来实现。时间复杂度还是一次树遍历O(n)，总的空间复杂度是栈空间O(logn)加上结果的空间O(n)，额外空间是O(logn)，总体是O(n)。
代码如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid + 1:])
return root
109. Convert Sorted List to Binary Search Tree
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
找到链表中点，建立root并递归处理左右两个新子list。但问题是对于一个链表我们是不能常量时间访问它的中间元素的。所以时间复杂度高。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
if not head:
return None
if not head.next:
return TreeNode(head.val)
walker = head
runner = head.next.next
while runner and runner.next:
walker = walker.next
runner = runner.next.next
head2 = walker.next
walker.next = None
root = TreeNode(head2.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(head2.next)
return root
这时候就要利用到树的中序遍历了，按照递归中序遍历的顺序对链表结点一个个进行访问，而我们要构造的二分查找树正是按照链表的顺序来的。思路就是先对左子树进行递归，然后将当前结点作为根，迭代到下一个链表结点，最后在递归求出右子树即可。整体过程就是一次中序遍历，时间复杂度是O(n)，空间复杂度是栈空间O(logn)加上结果的空间O(n)，额外空间是O(logn)，总体是O(n)。
代码如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
if not head:
return None
self.nextHead = head
count = 0
cur = head
while cur.next:
cur = cur.next
count += 1
return self.helper(0, count)
def helper(self, left, right):
if left > right:
return None
mid = (left + right) // 2
left = self.helper(left, mid - 1)
root = TreeNode(self.nextHead.val)
root.left = left
self.nextHead = self.nextHead.next
root.right = self.helper(mid + 1, right)
return root
173. Binary Search Tree Iterator
由于每次要使用next()返回下一个最小值，所以相当于中序遍历，我们使用一个stack来模拟中序遍历即可。
代码如下：
# Definition for a binary tree node
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.stack = []
self.current = root
def hasNext(self):
"""
:rtype: bool
"""
return self.stack or self.current
def next(self):
"""
:rtype: int
"""
while self.current:
self.stack.append(self.current)
self.current = self.current.left
node = self.stack.pop()
self.current = node.right
return node.val
# Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())
网友评论