leetcode 每天进步一道

[color=rgba(0, 0, 0, 0.65)]Given two binary trees, write a function to check if they are the same or not.

[color=rgba(0, 0, 0, 0.65)]Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

[color=rgba(0, 0, 0, 0.65)]Example 1:

Input:     1         1          / \       / \         2   3     2   3        [1,2,3],   [1,2,3]Output: true

[color=rgba(0, 0, 0, 0.65)]Example 2:

Input:     1         1          /           \         2             2        [1,2],     [1,null,2]Output: false

[color=rgba(0, 0, 0, 0.65)]Example 3:

Input:     1         1          / \       / \         2   1     1   2        [1,2,1],   [1,1,2]Output: false比较两个树是否相同，包括判断结构和节点的值，同样还是用到递归，加上了空节点的判断可以避免访问空指针# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None class Solution:    def isSameTree(self, p, q):        """        :type p: TreeNode        :type q: TreeNode        :rtype: bool        """        if p == None and q ==None:            return True        if p == None or q == None:#[1,2][1,null,2]            return False        if p.val == q.val:            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)        else :            return False# Definition for a binary tree node.

class Solution:
    # @param {TreeNode} p
    # @param {TreeNode} q
    # @return {boolean}
    def isSameTree(self, p, q):
        if p==q==None:
            return True
        if None in [p,q]:
            return False
        if p.val!=q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

LeetCode 14. Longest Common Prefix

以第一个string为标准，依次判断是否是前缀，如果不是就减一，直到为前缀。
思路：

找出所有字符串共同的前缀。以第一个字符串为标的，依次进行比较。
设置共同前缀的index为0，最小长度是所有字符串长度中最小的那个。依次比较strs中的元素，如果不等，就返回第一个字符串到index长度的slice。index加一，直至大于最小长度。

1.我们取出strs中的前两个字符串strs[0]和strs[1]，计算出它们的公共最长前缀LCS1 = lcs(strs[0], strs[1])

2.再取出strs中的第三个字符串strs[2]，计算出LCS1和strs[2]的公共最长前缀LCS2 = lcs(LCS1, strs[2]) = lcs(lcs(strs[0], strs[1]), strs[2])) = lcs(strs[0], strs[1], strs[2])，也就是说LCS2不仅是LCS1和strs[2]的公共最长前缀，也是strs[0], strs[1]和strs[2]的公共最长前缀

3.以此类推，假设strs的长度为4, 我们可以得到整个strs字符串数组的公共最长前缀LCS = lcs(lcs(lcs(strs[0], strs[1]), strs[2]), strs[3]那么剩下的工作就是写出函数lcs，然后在主函数longestCommonPrefix中循环调用这个lcs函数就可以了。代码如下：

public class Solution {
    private String lcs(String str1, String str2) {
        int rightBoundary = 0;
        int minLength = Math.min(str1.length(), str2.length());
        while(rightBoundary < minLength && str1.charAt(rightBoundary) == str2.charAt(rightBoundary)) {
            rightBoundary++;
        }
        return str1.substring(0, rightBoundary);
    }
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) return "";

        String previousLongestCommonPrefix = strs[0];
        for(int i = 1; i < strs.length; i++) {
            previousLongestCommonPrefix = lcs(previousLongestCommonPrefix, strs[i]);
        }
        return previousLongestCommonPrefix;
    }
}