中等题
1、面试题 04.05. 合法二叉搜索树 https://leetcode-cn.com/problems/legal-binary-search-tree-lcci/
考点：
1、按题意思是要比较当前节点和左右子树的值，也就是先要计算出左右子树的列表，才可知当前节点是否满足要求。 由此可知为后序遍历
2、（技巧）每次节点比较时，只要和左右子树的集合比较即可，所以迭代要返回当前节点子树的结合
3、（注意）需要考虑到 左右子树为空，左子树为空，右子树为空，左右子树均不为空等情况
class Solution:
def helper(self, root, result):
if root == None:
return []
l_list = self.helper(root.left, result)
r_list = self.helper(root.right, result)
print(str(root.val) + "*" + str(l_list) + "*" + str(r_list))
if l_list == [] and r_list == []:
return [root.val]
elif l_list == [] and r_list and root.val < min(r_list):
r_list.append(root.val)
return r_list
elif r_list == [] and l_list and root.val > max(l_list):
l_list.append(root.val)
return l_list
elif ((l_list and root.val > max(l_list)) and (r_list and root.val < min(r_list))):
l_list.extend(r_list)
l_list.append(root.val)
return l_list
else:
result.append(False)
def isValidBST(self, root: TreeNode) -> bool:
result = []
self.helper(root, result)
return False if False in result else True
2、面试题 16.19. 水域大小 https://leetcode-cn.com/problems/pond-sizes-lcci/
考点：
1、典型的二维数组 深度搜索问题，根据找到的某个位置，深度搜索满足条件的块
class Solution:
def helper(self, pos, now_pos, land):
row = len(land)
col = len(land[0])
i, j = pos
for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1), (i-1, j-1), (i+1, j-1), (i-1, j+1), (i+1, j+1)]:
if 0 <= x < row and 0 <= y < col and land[x][y] == 0 and (x, y) not in now_pos:
now_pos.append((x, y))
self.helper((x, y), now_pos, land)
return now_pos
def pondSizes(self, land: List[List[int]]) -> List[int]:
row = len(land)
col = len(land[0])
haved = []
result = []
for i in range(row):
for j in range(col):
if land[i][j] == 0 and (i, j) not in haved:
now_pos = []
now_pos.append((i, j))
self.helper((i, j), now_pos, land)
result.append(len(now_pos))
haved.extend(now_pos)
result.sort()
return result
3、面试题 04.06. 后继者 https://leetcode-cn.com/problems/successor-lcci/
考点
1、二叉树的中序遍历
2、（注意） 递归方法中设中间值和判断逻辑都在中序位置， 开始只做叶子节点返回值处理
原文：https://www.cnblogs.com/pyclq/p/13861835.html