16-20题

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))