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的兩個(gè)數(shù)字
輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S，在數(shù)組中查找兩個(gè)數(shù)退唠，是的他們的和正好是S，如果有多對(duì)數(shù)字的和等于S荤胁，輸出兩個(gè)數(shù)的乘積最小的瞧预。
排序數(shù)組可以在查找時(shí)進(jìn)行優(yōu)化。
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仅政、順時(shí)針打印矩陣
想了一會(huì)沒想出來垢油，百度了別人的思路，不斷旋轉(zhuǎn)矩陣圆丹，自己實(shí)現(xiàn)
class Solution:
def turn(self, matrix):
'''旋轉(zhuǎn)矩陣'''
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滩愁、二叉樹的下一個(gè)節(jié)點(diǎn)
給定一個(gè)二叉樹和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回辫封。注意硝枉，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)，同時(shí)包含指向父結(jié)點(diǎn)的指針倦微。
想了一會(huì)妻味，最笨的辦法就是寫一個(gè)中序遍歷，存到列表里欣福，然后找該節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)责球。然后上網(wǎng)查了一下，分為三種情況：
1、二叉樹是空雏逾，返回None
2嘉裤、該節(jié)點(diǎn)存在右子樹，一直沿著指向左子結(jié)點(diǎn)的指針找到的葉子節(jié)點(diǎn)即為下一個(gè)節(jié)點(diǎn)
3栖博、若不存在右子樹屑宠，如果該節(jié)點(diǎn)是左子節(jié)點(diǎn)，返回它的父節(jié)點(diǎn)笛匙，如果該節(jié)點(diǎn)是右子節(jié)點(diǎn)侨把，返回父節(jié)點(diǎn)的父節(jié)點(diǎn)
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、判斷一棵樹是不是左右對(duì)稱的樹
將根節(jié)點(diǎn)的右子樹整個(gè)翻轉(zhuǎn)妹孙，再判斷跟根節(jié)點(diǎn)的左子樹是不是相同就可以了
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))
