leetcode

Merge Two Binary Trees

Merge Two Binary Trees

Clean Version - 92ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 and t2:
            root = TreeNode(t1.val + t2.val)
            root.left = self.mergeTrees(t1.left, t2.left)
            root.right = self.mergeTrees(t1.right, t2.right)
            return root
        else:
            return t1 or t2

leet code

leetcode

Longest Substring with At Least K Repeating Characters

Longest Substring with At Least K Repeating Characters

Set Version - 36ms

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        for c in set(s):
            if s.count(c) < k:
                return max(self.longestSubstring(t, k) for t in s.split(c))
        return len(s)

test code

1
2
3
4
5
6
7
8
9
In [87]: s = 'aaabb'
In [88]: s.split('a')
Out[88]: ['', '', '', 'bb']
In [89]: k = 3
In [90]: ss = Solution(); t = ss.longestSubstring(s, k); print(t)
3

leet code

leetcode

Serialize and Deserialize Binary Tree

Serialize and Deserialize Binary Tree

Recursive Preorder Version - 120ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        vals = []
        def convert(node):
            if node:
                vals.append(str(node.val))
                convert(node.left)
                convert(node.right)
            else:
                vals.append('#')
        convert(root)
        return ' '.join(vals)
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        def convert():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = convert()
            node.right = convert()
            return node
        vals = iter(data.split())
        return convert()        
        
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

leet code

leetcode

Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

Recursive Version - 148ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if inorder:
            idx = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[idx])
            root.left = self.buildTree(preorder, inorder[0:idx])
            root.right = self.buildTree(preorder, inorder[idx+1:])
            return root

test code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
In [39]: class TreeNode:
    ...:     def __init__(self, x):
    ...:         self.val = x
    ...:         self.left = None
    ...:         self.right = None
In [50]: # Definition for a binary tree node.
    ...: # class TreeNode:
    ...: #     def __init__(self, x):
    ...: #         self.val = x
    ...: #         self.left = None
    ...: #         self.right = None
    ...:
    ...: class Solution:
    ...:     def buildTree(self, preorder, inorder):
    ...:         """
    ...:         :type preorder: List[int]
    ...:         :type inorder: List[int]
    ...:         :rtype: TreeNode
    ...:         """
    ...:         if inorder:
    ...:             idx = inorder.index(preorder.pop(0))
    ...:             root = TreeNode(inorder[idx])
    ...:             root.left = self.buildTree(preorder, inorder[0:idx])
    ...:             root.right = self.buildTree(preorder, inorder[idx+1:])
    ...:             return root
    
In [52]: pre_o = [3,9,20,15,7]
In [53]: in_o = [9,3,15,20,7]
In [54]: s = Solution(); t = s.buildTree(pre_o, in_o); print(t)
<__main__.TreeNode object at 0x10d8128d0>
In [55]: t.right.val
Out[55]: 20
In [56]: t.right.left.val
Out[56]: 15
In [57]: t.right.right.val
Out[57]: 7

leet code