Medium

2. Add Two Numbers

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = node = ListNode(0)
        carry = 0
        while l2 or l1 or carry:
            x_val = l1.val if l1 else 0
            y_val = l2.val if l2 else 0
            s = x_val + y_val + carry
            if s >= 10:
                s -= 10
                carry = 1
            else:
                carry = 0
            node.next = ListNode(s)
            l1 = l1 and l1.next
            l2 = l2 and l2.next
            node = node.next
        return dummy.next

144. Binary Tree Preorder Traversal

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

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root == None:
            return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

144. Binary Tree Preorder Traversal

class Solution:
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans, node = [],[root]
        while node:
            now = node.pop()
            if now:
                ans.append(now.val)
                node.extend([now.right, now.left])

94. Binary Tree Inorder Traversal

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

class Solution:
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        if root is not None:
            stack = []
            while stack or root is not None:
                if root is not None:
                    stack.append(root)
                    root = root.left
                else:
                    root = stack.pop()
                    result.append(root.val)
                    root = root.right
        return result

3. Longest Substring Without Repeating Characters

int lengthOfLongestSubstring(char* s) {
    int map[256] = {0};
    int result = 0;
    int i = 0;
    int left = 0;
    while(*(s+i)!='\0'){
        if(map[*(s+i)] == 0 || map[*(s+i)]<left){
            map[*(s+i)] = i+1;
        }else{
            left = map[*(s+i)];
            map[*(s+i)] = i+1;
        }
        result = (i-left+1)>result? (i-left+1): result;
        i++;
    }
    return result;
}

338. Counting Bits

class Solution:
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        ans = [0]
        for x in range(1, num + 1):
            ans += ans[x >> 1] + (x & 1),
        return ans