[leetcode]第十六部分(095+097-102)

95-Unique Binary Search Trees II

问题难度: ♣ ♣ ♣

问题描述

给定一个整数n, 生成所有由1...n构成的/结构上唯一的BST's(binary search tree, 二叉检索树).

示例

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:上面的输出对应下面5个唯一的BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解题思路

这道题目与上周做的第96题有一定的相似之处, 只不过这一次需要把具体的遍历路径返回. 首先, 我们将i从序列1...n中取出, 并将其作为当前树的根节点. 然后可以使用i-1个元素作为左树的元素, 剩下的n-i个元素作为右子树的元素. 正如我们之前讨论的, 这会生成G(i-1)中不同的左子树和G(n-i)种不同的右子树, 其中G是笛卡尔数.

现在, 我们对于序列1...i-1重复上面的步骤来构建所有的左子树, 然后对于i+1...n来构建所有的右子树.

这样,我们就可以得到根i和两个可能的左子树和右子树列表. 最后一步是遍历两个列表来将左子树和右子树连接到根的两边.

时间复杂度: 主要的计算花在给定一个根之后构造所有可能的子树, 将会调用n次, 时间复杂度为nG(n).

代码

# 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 generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        ans = list()
        return self.generateTreesRec(1, n) if n >= 1 else ans

    def generateTreesRec(self, start, end):
        if start > end:
            return [None,]
        ans = []
        for i in range(start, end + 1): # pick i as root
            left_trees = self.generateTreesRec(start, i-1)
            right_trees = self.generateTreesRec(i+1, end)

            for left in left_trees:
                for right in right_trees:
                    cur_tree = TreeNode(i)
                    cur_tree.left = left
                    cur_tree.right = right
                    ans.append(cur_tree)
        return ans

97- Interleaving String

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

给定三个字符串s_1, s_2s_3, 判断s_3是否由s_1s_2交叉构成.

示例1

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

示例2

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

解题思路

方法1: 暴力破解法

最简单的想法是找到两个给定字符串s_1s_2的所有可能交叉字符串. 我们使用递归来实现这个方法. 针对s_1当前字符, 可以将其添加到字符串末尾, 判断是否与s_3相等, 也可以使用s_2当前的字符, 将其添加到末尾, 只要有一个满足条件即可, 不过有一点需要注意的是: 即使当前满足相等的条件, 那么也要看是否已经s_1s_2是否也已经到了末尾.

时间复杂度为O(2^{m+n}), 其中mn分别为s_1s_2的长度.

提交尝试了一下, 果然超出时间限制了…

方法2: 带记忆的暴力破解

思考一下, 其实上面的方法其实会进行大量重复的工作, 那么我们想想, 是否可以存储一下已经比较过的结果呢? 在上面方法的基础上,使用一个memo[i][j]的二维数组存储一下已经比较过的字符串即可.

嗯, 时间复杂度依旧是O(2^{m+n}), 但是由于减少了许多无畏的比较, 减少了实际计算的时间.然后AC了.

方法3: 动态规划法(二维数组)

老规矩, 之前看到过一种说法…只要是字符串相关的题目都可以用动态规划法解决.

动态规划法第一步: 将问题使用数学的形式表达出来–使用一个二维数组dp[i][j]来记录到s_1的第i位和到s_2的第j位(从1开始计数),是否与s_3的前i+j+2的字符串交叉匹配. 下面来看看递推公式:
– 如果i==0 and j==0, 那么dp[i][j] = True
– 如果i==0 and j>0, 那么dp[i][j] = dp[i][j-1] and s2[j-1] == s[i+j-1]
– 如果i>0 and j == 0, 那么dp[i][j] = dp[i-1][j] and s1[i-1] == s[i+j-1]
– 其它情况: dp[i][j] = (dp[i-1][j] and s1[i-1] == s[i+j-1]) or (dp[i][j-1] and s2[j-1] == s[i+j-1])

最后返回dp[len(s1)][len(s2)]即可. 此时时间复杂度为O(m*n), 空间复杂度为O(m*n).

方法4: 动态规划法(一维数组)

看看发现其实可以只使用一个一维数组来存储动态形式, 因为在前一个方法中, 每次只用到了一个之前的值.其实我们每次只需要维护一个长度为O(n)的一维数组即可.

此时时间复杂度为O(m*n), 空间复杂度为O(n).

代码

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1) + len(s2) != len(s3):
            return False
        def check(s1, s2, s3, i, j, res):
            if res == s3 and i == len(s1) and j == len(s2):
                return True
            ans = False
            if i < len(s1):
                ans = ans or check(s1, s2, s3, i+1, j, res + s1[i])
            if j < len(s2):
                ans = ans or check(s1, s2, s3, i, j+1, res + s2[j])
            return ans
        return check(s1, s2, s3, 0, 0, "")

    def isInterleaveMemo(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1) + len(s2) != len(s3):
            return False
        def check(s1, s2, s3, i, j, k, memo):
            if i == len(s1):
                return s2[j:] == s3[k:]
            if j == len(s2):
                return s1[i:] == s3[k:]
            if memo[i][j] >= 0:
                return True if memo[i][j] == 1 else False
            ans = False
            if (s1[i] == s3[k] and check(s1, s2, s3, i+1, j, k+1, memo) or (s2[j] == s3[k] and check(s1, s2, s3, i, j+1, k+1, memo))):
                ans = True
            memo[i][j] = 1 if ans else 0
            return ans
        memo = [[-1 for _ in range(len(s2))] for _ in range(len(s1))]
        return check(s1, s2, s3, 0, 0, 0, memo)

    def isInterleaveDP(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1) + len(s2) != len(s3):
            return False
        dp = [[False for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]
        for i in range(len(s1)+1):
            for j in range(len(s2)+1):
                if i == 0 and j == 0:
                    dp[i][j] = True
                elif i == 0:
                    dp[i][j] = dp[i][j-1] and s2[j-1] == s3[i+j-1]
                elif j == 0:
                    dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i+j-1]
                else:
                    dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
        return dp[len(s1)][len(s2)]

    def isInterleaveDP1D(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1) + len(s2) != len(s3):
            return False
        dp = [False for _ in range(len(s2)+1)]
        for i in range(len(s1)+1):
            for j in range(len(s2)+1):
                if i == 0 and j == 0:
                    dp[j] = True
                elif i == 0:
                    dp[j] = dp[j-1] and s2[j-1] == s3[i+j-1]
                elif j == 0:
                    dp[j] = dp[j] and s1[i-1] == s3[i+j-1]
                else:
                    dp[j] = (dp[j] and s1[i-1] == s3[i+j-1]) or (dp[j-1] and s2[j-1] == s3[i+j-1])
        return dp[len(s2)]
s1 =  "aac"
s2 = "abad"
s3 = "aabadac"
s = Solution()
print(s.isInterleaveDP1D(s1, s2, s3))
True

98-Validate Binary Search Tree

问题难度: ♣ ♣ ♣

问题描述

给定一个二叉树, 判断其是否是一个有效的BST(binary search tree, 搜索二叉树).

BST的定义如下:
– 节点的左子树只能包含小于该节点值的键
– 节点的右子树只能包含大于该节点值的键
– 左子树和右子树必须也是二进制检索树

示例1

Input:
    2
   / \
  1   3
Output: true

示例2

    5
   / \
  1   4
     / \
    3   6
Output: false
解释: 输入为 [5,1,4,null,null,3,6].根节点的值为5, 但是其右子树的节点为4.

解题思路

可以换个思路: 使用中序遍历的方法来判断数组是否升序排列即可.

# 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 isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        cur = root
        stack = list()
        last_val = None
        while cur is not None or len(stack) > 0:
            while cur is not None:
                stack.append(cur)
                cur = cur.left
            cur = stack[-1]
            stack = stack[:-1]
            if last_val is None:
                last_val = cur.val
            else:
                if last_val < cur.val:
                    last_val = cur.val
                else:
                    return False
            cur = cur.right
        return True

99-Recover Binary Search Tree

问题难度: ♣ ♣ ♣ ♣ ♣

问题描述

一个BST(binary search tree, 检索二叉树)的两个元素错误地进行交换了.

在不修改其结构的情形下恢复树.

示例1

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例2

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

扩展
– 可以直接使用O(n)的空间
– 能否想到一个常数空间的解决方案.

解题思路

这道题目可以沿用上面题目的想法, 搜索二叉树其实可以看做是一个中序遍历的升序数组. 恢复搜索二叉树只需要找到异常值,然后交换即可.如果前一个元素的值大于当前元素的值时, 标识为异常值, 分为下面集中情况:
– 如果前面没有异常值, 则将前一个元素表示为第一个异常值;
– 如果前面已经有异常值了, 那么则需要将当前的元素值与第一个异常值交换然后返回即可

如果到最后一直只有1个异常值的话, 那么则需要将第一个异常值和其后面的值进行交换即可.

因此, 这里我们需要使用3个变量来存储对应的值:
error_node: 第一个异常值
error_next_node: 第一个异常值后面的节点
last_node: 前一个节点

代码

# 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 recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        cur = root
        stack = list()
        last_node = None
        error_node = None
        error_next_node = None
        while cur is not None or len(stack) > 0:
            while cur is not None:
                stack.append(cur)
                cur = cur.left
            cur = stack[-1]
            stack = stack[:-1]
            if last_node is None:
                last_node = cur
            else:
                if last_node.val < cur.val:
                    last_node = cur
                else:
                    if error_node is None:
                        error_node = last_node
                        error_next_node = cur
                    else:
                        tmp = error_node.val
                        error_node.val = cur.val
                        cur.val = tmp
                        return
                    last_node = cur
            cur = cur.right
        if error_node is not None and error_next_node is not None:
            tmp = error_node.val
            error_node.val = error_next_node.val
            error_next_node.val = tmp

100-Same Tree

问题难度: ♣

问题描述

给定两个二叉树, 实现一个函数来检测它们是否相同.

如果两个二叉树结构上相同并且节点相同的话就表明这两个棵树相同.

示例1

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

示例2

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

示例3

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

解题思路

两棵树相等, 需要满足三个条件:

  • 值相等
  • 左子树结构相同
  • 右子树结构相同

因此, 当当前值相等时, 再继续比较左子树和右子树, 直到两棵树都遍历到叶子节点为止.

代码

# 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 isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p is None:
            return q is None
        if q is None:
            return False
        if p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False

101-Symmetric Tree

问题难度: ♣

问题描述

给定一个二叉树, 判断其是否是本身的镜像(也就是说: 关于中心点对称).
例如, 二叉树 [1,2,2,3,4,4,3] 是对称的:

        1
       / \
      2   2
     / \ / \
    3  4 4  3

但是 [1,2,2,null,3,null,3] 则不是对称的:

        1
       / \
      2   2
       \   \
       3    3

注意:

如果能同时提供递归和迭代的做法有加分哦~

解题思路

方法1: 递归法

与上一题的解法有点类似:只需要判断根节点的左子树和右子树是否相等即可.

方法2: 迭代法

# 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 isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def checkSame(left, right):
            if left is None:
                return right is None
            if right is None:
                return False
            if left.val == right.val:
                return checkSame(left.left, right.right) and checkSame(left.right, right.left)
            else:
                return False
        if root is not None:
            return checkSame(root.left, root.right)
        else:
            return True

102. Binary Tree Level Order Traversal

问题难度: ♣ ♣ ♣

问题描述

给定一个二叉树, 返回其节点的层次顺序遍历的节点值(例如, 从左到右, 一层一层).

例如, 给定一个二叉树[3,9,20,null,null,15,7].

    3
   / \
  9  20
    /  \
   15   7

返回其层次顺序遍历的结果如下:

[
  [3],
  [9,20],
  [15,7]
]

解题思路

整体上看, 需要把节点的左子树的值和右子树的值放在同一级别就行了, 因此可以使用迭代的方法进行求解: 使用两个list分别存储当前层和下一层, 其中下一层完全依赖于当前层的leftright. 直到到达底部为止.

代码

# 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 levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        total_ans = list()
        total_ans.append([root.val])
        stack = [root.left, root.right]
        next_stack = stack
        while len(next_stack) > 0:
            next_stack = list()
            ans = list()
            for i in range(len(stack)):
                cur_node = stack[i]
                if cur_node is not None:
                    ans.append(cur_node.val)
                    next_stack.append(cur_node.left)
                    next_stack.append(cur_node.right)
            stack = next_stack
            if len(ans) > 0:
                total_ans.append(ans)
        return total_ans
打赏

mickey

记录生活,写给几十年后的自己。