【LeetCode】【Python题解】Single Number & Maximum Depth of Binary Tree

今天做了三道LeetCode上的简单题目,每道题都是用c++和Python两种语言写的,因为c++版的代码网上比较多,所以就只分享一下Python的代码吧,刚学完Python的基本语法,做做LeetCode的题目还是不错的,对以后找工作面试也有帮助!


刚开始就从AC率最高的入手吧!


1.Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

开始纠结于线性时间复杂度和不要额外的存储空间,思路是遍历一遍数组,想象成翻硬币,碰到一次就翻面,再碰到就翻回来了,剩下的那个仍是背面的就是只出现一次的。但是这种思路就势必要有额外的存储空间。后来看了别人的思路,原来全部异或就可以了,因为A XOR A =0,0 XOR any = any,简单多了。

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        result = 0
        for i in A:
            result = result ^ i
        return result



2.Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.


递归寻找左子树和右子树的深度,取二者较大的,再加上根的深度1,即为答案。

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return an integer
    def maxDepth(self, root):
        if root is None:
            return 0
        else:
            return max(self.maxDepth(root.left),self.maxDepth(root.right))+1


【LeetCode】【Python题解】Single Number & Maximum Depth of Binary Tree

上一篇:C++: Find height of a Binary Tree


下一篇:Java虚拟机工作原理具体解释