16、二叉树的深度
# 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 maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
else:
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
17、和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
排序数组可以在查找时进行优化。
class Solution:
def FindNumbersWithSum(self, array, tsum):
rst = [tsum, tsum]
for i in range(len(array)):
for j in range(i, len(array)):
if array[i] + array[j] == tsum:
if array[i]*array[j] < rst[0]*rst[1]:
rst = [array[i], array[j]]
break
if array[i] + array[j] > tsum:
break
if rst == [tsum, tsum]:
return False
return rst
18、顺时针打印矩阵
想了一会没想出来，百度了别人的思路，不断旋转矩阵，自己实现
class Solution:
def turn(self, matrix):
'''旋转矩阵'''
length = len(matrix[0])
height = len(matrix)
rst = []
for i in range(length):
cur = []
for j in range(height):
cur.append(matrix[j][i])
rst.append(cur)
return rst[::-1]
def printMatrix(self, matrix):
rst = []
while matrix:
for i in matrix[0]:
rst.append(i)
matrix.pop(0)
if matrix:
matrix = self.turn(matrix)
return rst
19、二叉树的下一个节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
想了一会，最笨的办法就是写一个中序遍历，存到列表里，然后找该节点的上一个节点。然后上网查了一下，分为三种情况：
1、二叉树是空，返回None
2、该节点存在右子树，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点
3、若不存在右子树，如果该节点是左子节点，返回它的父节点，如果该节点是右子节点，返回父节点的父节点
class Solution:
def GetNext(self, pNode):
if not pNode: return None
if pNode.right:
pNode = pNode.right
while pNode.left:
pNode = pNode.left
return pNode
else:
while pNode.next:
if pNode == pNode.next.left:
return pNode.next
pNode = pNode.next
return None
20、判断一棵树是不是左右对称的树
将根节点的右子树整个翻转，再判断跟根节点的左子树是不是相同就可以了
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
def reverseTree(root):
if root:
reverseTree(root.left)
reverseTree(root.right)
root.left, root.right = root.right, root.left
return root
else:
return root
def isSameTree(p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p==None and q==None:
return True
if not p or not q:
return False
if p.val == q.val:
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
else:
return False
return isSameTree(root.left, reverseTree(root.right))
