链表

链表分为单（向）链表和双（向）链表。顾名思义，单链表就是单一方向遍历的链表结构，双链表就是双向遍历的链表结构。

单链表

在python中可以这么定义单链表节点。

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        temp = self
        s = ''
        while temp:
            s += str(temp.val) + ' ---> '
            temp = temp.next
        s += 'None'
        return s
    
    @classmethod
    def generate(cls, nums):
        result = temp = ListNode(nums[0])
        for i in nums[1:]:
            temp.next = ListNode(i)
            temp = temp.next
        return result

链表长度为n时，遍历的时间复杂度是O(n)，插入的时间复杂度是O(1), 删除的时间复杂度是O(n)。

插入

在链表之间插入。

l1 = ListNode(1)
l2 = ListNode(2)
l1.next = l2
'''
1 ->  2 -> None
'''

现在有个一新的节点l3，将它插入到链表中我们只要。

l3 = ListNode(3)
l3.next = l2
l1.next = l3
'''
1 -> 3 -> 2 -> None
'''

在链表前或者末尾插入，都是比较简单的。

# 链表前
l4 = ListNode(4)
l4.next = l1
'''
4 -> 1 -> 3 -> 2 -> None
'''
# 链表后
l5 = ListNode(5)
l2.next = l5
'''
4 -> 1 -> 3 -> 2 -> 5 -> None
'''
# 或者
l5 = ListNode(5)
while l1.next:
    l1 = l1.next
l1.next = l5
'''
4 -> 1 -> 3 -> 2 -> 5 -> None
'''

删除

l1 = ListNode(1)
l2 = ListNode(2)
l3 = ListNode(3)
l1.next = l2   
l2.next = l3
'''
1 -> 2 -> 3 -> None
'''

删除l2可以这样

l1.next = l3
'''
1 -> 3 -> None
'''

删除结点的时间复杂度是O(n)，空间复杂度为O(1)。

设计链表

class MyLinkedList(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.length = 0
        self.head = ListNode(0)

    def get(self, index):
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        :type index: int
        :rtype: int
        """
        if index >= self.length:
            return -1
        head = self.head
        for _ in range(index + 1):
            head = head.next
        return head.val

    def addAtHead(self, val):
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        :type val: int
        :rtype: None
        """
        self.addAtIndex(0, val)

    def addAtTail(self, val):
        """
        Append a node of value val to the last element of the linked list.
        :type val: int
        :rtype: None
        """
        self.addAtIndex(self.length, val)

    def addAtIndex(self, index, val):
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        :type index: int
        :type val: int
        :rtype: None
        """
        if index > self.length:
            return

        if index < 0:
            index = 0
        node = ListNode(val)
        head = self.head
        for i in range(index):
            head = head.next

        node.next = head.next
        head.next = node
        self.length += 1

    def deleteAtIndex(self, index):
        """
        Delete the index-th node in the linked list, if the index is valid.
        :type index: int
        :rtype: None
        """
        if index >= self.length or index < 0:
            return
        head = self.head
        while index:
            index -= 1
            head = head.next
        head.next = head.next.next
        self.length -= 1


linkedList = MyLinkedList()
linkedList.addAtHead(1)
print(linkedList.head)
linkedList.addAtTail(3)
print(linkedList.head)
linkedList.addAtIndex(1, 2)
print(linkedList.head)
print(linkedList.get(1))
linkedList.deleteAtIndex(1)
print(linkedList.head)
print(linkedList.get(1))

双指针

判断是否有环

给定一个链表，判断链表中是否有环，返回链表开始入环的第一个节点。

思路：
定义两个指针，一个走的快，一个走的慢。如果链表中存在环，那么快指针肯定会再次追上慢指针（套圈）。
两个指针相遇的点记作点A。再定义一个指针再从链表头出发，慢指针从点A出发，它们相遇的地方记作点B。
点B就是链表开始入环的第一个节点。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        fast = head
        slow = head
        while slow and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                fast = head
                while fast != slow:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None


l0 = ListNode(0)
l1 = ListNode(1)
l2 = ListNode(2)
l3 = ListNode(3)
l4 = ListNode(4)

l0.next = l1
l1.next = l2
l2.next = l3
l3.next = l4
l4.next = l1

s = Solution().detectCycle(l0)
print(s.val)

相交链表

找到两个单链表相交的起始节点。

思路：
x + y = y + x。同时遍历两个条链表，短的链表先遍历完，再将它和长的链表相接也就是x + y。同理长的链表遍历完的时候，再将它和短的链表相接也就是y + x。这样一来，就解决了遍历时两条链表长度不一致的问题。遍历过程中，节点相同的就是交点。

两条链表没有交点的情况也同样适用。

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        x = headA
        y = headB
        while x != y:
            x = x.next if x else headB
            y = y.next if y else headA
        return x

l1 = ListNode(4)
l2 = ListNode(1)
l3 = ListNode(8)
l4 = ListNode(4)
l5 = ListNode(5)
l1.next = l2
l2.next = l3
l3.next = l4
l4.next = l5

l6 = ListNode(5)
l7 = ListNode(0)
l8 = ListNode(1)
l6.next = l7
l7.next = l8
l8.next = l3

print(Solution().getIntersectionNode(l1, l6))

删除倒数第N个节点

删除链表的倒数第n个节点，并且返回链表的头结点。n保证是有效值。

思路：
定义两个指针，一个负责定位删除的元素的指针x，一个负责辅助定位的指针y。
先让y指针走n步，再让x和y，同时遍历。当y指向链表的最后一项时，x刚好指向要删除的元素的前一项。这样可以利用x.next = x.next.next删除x的下一项。

有一个情况需要考虑到，就是指针y走n步后，y已经为空，也就是n == 链表的长度，也就是要删除第一个数，结果直接返回head.next即可。

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head:
            return None
        x = y = head
        for _ in range(n):
            y = y.next
        if not y:
            return head.next
        while y.next:
            y = y.next
            x = x.next
        x.next = x.next.next
        return head
        

l = ListNode.generate([1, 2, 3, 4, 5])
print(Solution().removeNthFromEnd(l, 2))
l = ListNode.generate([1])
print(Solution().removeNthFromEnd(l, 1))
l = ListNode.generate([1, 2])
print(Solution().removeNthFromEnd(l, 1))
l = ListNode.generate([1, 2])
print(Solution().removeNthFromEnd(l, 2))

经典问题

反转链表

反转一个链表。

思路一：
双指针解法。定义一个指针result，配合参数head组成双指针。result必须先设为None。
随后遍历head。遍历head时，注意要记录一下head.next的值，这里定义一个temp来接收它。
然后就是反转。
head.next = result 把head下一个指向result，
result = head 同时更新一下result的位置，让result指向当前head所指向的位置。
最后更新一下head的位置，注意这时的head指向，不能使用head = head.next要用head = temp来更新head位置。
最后返回result即可。

这里说明一下result的初始值必须为None，因为反转后的链表的最后一项（也就是反转前的第一项）必须指向None。
result指针在第一次循环开始后，就紧跟在head的前面。

算法时间复杂度是O(n)，空间复杂度是O(1)。

思路二：
递归。递归的解法有点不好想。首先想，递归要什么时候返回值合适，应该是head.next为空的时候我们需要返回head的值，不能等到head为空了再返回，因为我们要保证head.next不为空才能进行反转。

1 -> 2 -> 3 -> 4 -> 5 -> None
拿上面的链表举例。刚开始head在1的位置，当进行递归时head的位置应该在5。反转时，我们还需要知道前一个节点，所以head应该在4的位置。给递归函数需要传head.next，这样既保证了递归，也保证了在head到4位置时，返回值是5 -> None这个链表。
此时的head的值为 4 —> 5 -> None。返回值后我们知道需要反转了。
首先让5 -> 4，head.next.next = head，
再将4 -> 5之间的联系断开，不然有环。head.next = None
就得到了5 -> 4。

当head为空时，直接返回head。

算法时间复杂度是O(n)，空间复杂度是O(n)。

class Solution(object):
    # 循环
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        result = None
        while head:
            temp = head.next
            head.next = result
            result = head
            head = temp
        return result
    
    # 递归
    def reverseList_2(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        result = self.reverseList_2(head.next)
        head.next.next = head
        head.next = None
        return result

移除链表元素

删除链表中等于给定值 val 的所有节点。

思路：
定义两个指针result和pre，它们的next都指向head。遍历pre，当pre.next不为空时，判断pre.next.val和val的值是否一致，如果一致，pre.next被删除掉，pre.next = pre.next.next，不一致，pre前进一步，pre = pre.next。循环结束后result.next即所求。

主要考虑到删除当前元素时，需要知道前一个元素的指针才能删除。所以要，pre.next = head。

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        result = pre = ListNode(None)
        pre.next = head
        while pre.next:
            if pre.next.val == val:
                pre.next = pre.next.next
            else: 
                pre = pre.next
        return result.next

奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

思路：
定义两个ListNode，odd（奇）和even（偶），和他们各自的head，odd_head和even_head。
遍历链表head，第一次循环时，链表的第一项默认是奇数项，所以odd.next = head, odd前进一步odd = odd.next。
链表的第一项默认是奇数项，第二项就是偶数项，所以even的下一项就是head.next，even.next = head.next，even前进一步。
这时候，head应该前进两步，要使用head = head.next.next，但是当head.next为空时（遍历到最后一项），会出错，这时应该直接将head置为空。
循环结束后，得到两条链表，odd_head和even_head。将even_head接在odd_head后就好了。odd.next = odd_head.next
odd_head.next即所得。

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        odd = odd_head = ListNode(None)
        even = even_head = ListNode(None)
        while head:
            odd.next = head
            odd = odd.next
            even.next = head.next
            even = even.next

            head = head.next.next if even else None
        odd.next = even_head.next
        return odd_head.next

回文链表

判断一个链表是否为回文链表。

思路一：
遍历链表，然后利用数组存放链表的值。最后判断数组是否是回文就可以了。此方法的算法时间复杂度是O(n)，空间复杂度也是O(n)，因为开辟了链表大小的数组。

思路二：
类似反转链表。例如，链表
1 -> 2 -> 3 -> 2 -> 1 -> None
我们只需要将1 -> 2 -> 3的链表反转，再和剩下的链表进行比较，就可以了。
定义一个快指针fast，一个慢指针slow，一个控制反转的指针x。快指针一次走两步，慢指针一次走一步。
遍历链表，要保证fast和fast.next不为空，这时进行链表的反转操作。当循环结束时，fast指针可能在最后一个或者倒数第二个的位置即fast为空或者fast.next为空，这是由于链表长度有奇有偶导致的。所以当fast不为空时（链表项为奇数项），我们将slow后移动一步，slow = slow.next。这样我们就将链表从中间分开，得到一个slow链表，一个x链表（经过反转）。
slow：2 -> 1 -> None
x：2 -> 1 -> None
反转链表时，x所指的位置一直是都是slow的前一项。
再遍历链表slow判断值是否和x链表一致就可以得出是否是回文链表了。

算法时间复杂度是O(n)，空间复杂度是O(1)。

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        values = []
        while head:
            values.append(head.val)
            head = head.next
        return values == values[::-1]
    
     def isPalindrome_2(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return True
        fast = slow = head
        x = None
        while fast and fast.next:
            fast = fast.next.next
            temp = slow.next
            slow.next = x
            x = slow
            slow = temp
        if fast:
            slow = slow.next
        while slow:
            if slow.val != x.val:
                return False
            slow = slow.next
            x = x.next
        return True

双链表

双链表中节点的定义。

class DoublyListNode(object):
    def __init__(self, x):
        self.val = x
        self.pre = None
        self.next = None

插入

如果我们想在现有的结点prev之后，next之前插入一个新的结点cur，我们可以将此过程分为两个步骤：

cur.pre = prev
cur.next = next

prev.next = cur
next.pre = cur

与单链表类似，添加操作的时间和空间复杂度都是O(1)。

删除

删除之前添加在prev和next之间的节点cur。

1 2	prev.next = next next.pre = prev

删除操作的时间和空间复杂度都是O(1)。

小结

单链表和双链表相同点。

它们都无法在常量时间内随机访问数据。
它们都能够在O(1)时间内在给定结点之后或列表开头添加一个新结点。
它们都能够在O(1)时间内删除第一个结点。

再删除节点上，单链表和双链表稍有不同。

在单链表中，它无法获取给定结点的前一个结点，因此在删除给定结点之前我们必须花费O(N)时间来找出前一结点。
在双链表中，这会更容易，因为可以使用pre获取前一个结点。因此可以在O(1)时间内删除给定结点。

时间复杂度对照

练习

合并两个有序的链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        result = temp = ListNode(None)
        while l1 and l2:
            if l1.val <= l2.val:
                temp.next = l1
                l1 = l1.next
            else:
                temp.next = l2
                l2 = l2.next
            temp = temp.next
        temp.next = l1 if l1 else l2
        return result.next

两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

class Solution(object):
    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            result = pre = ListNode(None)
            carry = 0
            while l1 or l2 or carry:
                if l1:
                    carry += l1.val
                    l1 = l1.next
                if l2:
                    carry += l2.val
                    l2 = l2.next
                pre.next = ListNode(carry % 10)
                pre = pre.next
                carry //= 10
            return result.next

旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数。

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head:
            return head
        x = y = head
        n = 1
        while x.next:
            n += 1
            x = x.next
        x.next = head
        for _ in range(n - k % n - 1):
            y = y.next
        result = y.next
        y.next = None
        return result

队列

队列是先进先出（FIFO）的数据结构。

插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。删除（delete）操作也被称为出队（dequeue)。你只能移除第一个元素。

按顺序处理元素时，使用队列可能是一个很好的选择。

循环队列

普通队列，在存储变量时，会出现假溢出的情况，为了充分利用存储空间，克服这一现象，循环队列应运而生。

假溢出。
系统作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为”假溢出”。

解决方法：

将队列元素向前“平移”。
将队列看成首尾相连，即循环队列。

设计

class MyCircularQueue(object):

    def __init__(self, k):
        """
        Initialize your data structure here. Set the size of the queue to be k.
        :type k: int
        """
        self.k = k + 1
        self.q = [None] * self.k
        self.head = self.tail = 0

    def enQueue(self, value):
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if self.isFull():
            return False
        self.q[self.tail] = value
        self.tail = (self.tail - 1) % self.k
        return True

    def deQueue(self):
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        :rtype: bool
        """
        if self.isEmpty():
            return False
        self.head = (self.head - 1) % self.k
        return True

    def Front(self):
        """
        Get the front item from the queue.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        return self.q[self.head]

    def Rear(self):
        """
        Get the last item from the queue.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        return self.q[(self.tail + 1) % self.k]

    def isEmpty(self):
        """
        Checks whether the circular queue is empty or not.
        :rtype: bool
        """
        return self.head == self.tail

    def isFull(self):
        """
        Checks whether the circular queue is full or not.
        :rtype: bool
        """
        return (self.head + 1) % self.k == self.tail

Python中的队列

Python标准库中包含了四种队列，分别是queue.Queue、asyncio.Queue、multiprocessing.Queue和collections.deque。这里只讨论collections.deque。

collections.deque是双端队列（double-ended queue）的缩写，由于两端都能编辑，deque既可以用来实现栈（stack）也可以用来实现队列（queue）。

deque支持丰富的操作方法。

相比于list实现的队列，deque实现拥有更低的时间和空间复杂度。list实现在出队和入队时的空间复杂度大约为O(n)，deque在出队和入队时的时间复杂度是O(1)。

广度优先搜索

广度优先搜索（Breadth First Search）简称BFS，其中一个应用就是找到根节点距离目标节点的最短路径。最近接根节点的节点最先遍历。

在第k轮中将节点x添加到队列中，则根节点和节点x之间的最短距离刚好是k。

广度优先搜索遍历时，首先将根节点加入队列中，随后将临近根节点的节点依次加入到队列中，并将根节点推出队列，以此类推，新添加的节点不会被立即处理，而是被添加到队列的末尾，等待下一轮的处理。

节点的添加到队列的顺序和它们被处理的顺序完全相同，即先进先出（FIFO）。这是在BFS中应用队列的主要原因。

模板

模板一。

import collections


def BFS(node, target):
    # store all nodes which are waiting to be processed
    queue = collections.deque()

    # number of steps neeeded from root to current node
    step = 0

    # initialize
    # add root to queue;

    # find neighbors
    def neighbors(node):
        pass

    while queue:
        step += 1
        # iterate the nodes which are already in the queue
        for item in queue:
            if item == target:
                return step
            for n in neighbors(item):
                queue.append(n)
            queue.popleft()
    # there is no path from root to target
    return -1

模板二。
确保不会访问一个结点两次。可以在上面的代码中添加一个哈希集。

import collections


def BFS(node, target):
    # store all nodes which are waiting to be processed
    queue = collections.deque()

    # number of steps neeeded from root to current node
    step = 0

    used = set()

    # initialize
    # add root to queue;

    # find neighbors
    def neighbors(node):
        pass

    while queue:
        step += 1
        # iterate the nodes which are already in the queue
        for item in queue:
            if item == target:
                return step
            for n in neighbors(item):
                if n not in used:
                    used.add(n)
                    queue.append(n)
            queue.popleft()
    # there is no path from root to target
    return -1

有两种情况你不需要使用哈希集：

确定没有循环，例如，在树遍历中；
希望多次将结点添加到队列中。

岛屿数量

一个由’1’（陆地）和’0’（水）组成的的二维网格，计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，可以假设该网格的四条边均被水包围。

import collections


class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0
        islands = 0
        rows = len(grid)
        cols = len(grid[0])

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    islands += 1
                    grid[r][c] = '0'
                    queue = collections.deque([(r, c)])
                    while queue:
                        row, col = queue.popleft()
                        if row - 1 >= 0 and grid[row - 1][col] == '1':
                            queue.append((row - 1, col))
                            grid[row - 1][col] = '0'
                        if row + 1 < rows and grid[row + 1][col] == '1':
                            queue.append((row + 1, col))
                            grid[row + 1][col] = '0'
                        if col - 1 >= 0 and grid[row][col - 1] == '1':
                            queue.append((row, col - 1))
                            grid[row][col - 1] = '0'
                        if col + 1 >= 0 and grid[row][col + 1] == '1':
                            queue.append((row, col + 1))
                            grid[row][col + 1] = '0'
        
        return islands

打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字：’0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把’9’变为’0’，’0’变为’9’。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为’0000’ ，一个代表四个拨轮的数字的字符串。

列表deadends包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串target代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

import collections
class Solution(object):
    def openLock(self, deadends, target):
        """
        :type deadends: List[str]
        :type target: str
        :rtype: int
        """
        def neighbors(node):
            for i in range(4):
                for x in (-1, 1):
                    x = (int(node[i]) + x ) % 10
                    yield node[:i] + str(x) + node[i+1:]
        dead = set(deadends)
        if '0000' in dead:
            return -1
        queue = collections.deque([('0000', 0)])
        seen = { '0000' }
        while queue:
            node, step = queue.popleft()
            if node == target:
                return step
            if node in dead:
                continue
            for n in neighbors(node):
                if n not in seen:
                    seen.add(n)
                    queue.append((n, step + 1))
        return -1

完全平方数

给定正整数n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于n。你需要让组成和的完全平方数的个数最少。

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        """
        四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。
        推论：满足四数平方和定理的数n（四个整数的情况），必定满足 n=(4^a)(8b+7)
        """
        while n % 4 == 0:
            n /= 4
        if n % 8 == 7:
            return 4
        a = 0
        while a ** 2 <= n:
            b = int((n - a ** 2) ** 0.5)
            if a ** 2 + b ** 2 == n:
                return (not not a) + (not not b)
            a += 1
        return 3

01 矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。
解法一。

class Solution(object):
    def updateMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """
        rows = len(matrix)
        cols = len(matrix[0])

        deltas = [
            (1, 0 ), (-1, 0), (0, 1), (0, -1)
        ]
        unknown = set()

        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 1:
                    unknown.add((r, c))
        
        while unknown:
            new_unknown = set()
            for r, c in unknown:
                for dr, dc in deltas:
                    if 0 <= dr + r < rows and 0 <= dc + c < cols and (dr + r, dc + r) not in unkonwn:
                        matrix[r][c] = matrix[dr + r][dc + c] + 1
                        break
                else:
                    new_unknown.add((r, c))
            unknown = new_unknown
        return matrix

我有骄傲吗？

解法二。

import collections

class Solution(object):
    def updateMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[List[int]]
        """
        rows = len(matrix)
        cols = len(matrix[0])
        deltas = [ (0, 1), (0, -1), (1, 0), (-1, 0)]
        max_dist = rows + cols - 1
        queue = collections.deque()
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 1:
                    matrix[r][c] = max_dist
                else:
                    queue.append((r, c))
        
        while queue:
            r, c = queue.popleft()
            for dr, dc in deltas:
                if 0 <= dr + r < rows and 0 <= dc + c < cols: 
                    if matrix[r][c] + 1 < matrix[r + dr][c + dc]:
                        matrix[dr + r][dc + c] = matrix[r][c] + 1
                        queue.append((dr + r, dc + c))
        return matrix

栈

栈是先入后出（LIFO）的数据结构。

在LIFO数据结构中，将首先处理添加到队列中的最新元素。
与队列不同，栈是一个LIFO数据结构。通常，插入操作在栈中被称作入栈（push）。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈（pop），始终删除最后一个入栈的元素。

经典问题

有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return True
        stack = []
        match = {
            '{': '}',
            '[': ']',
            '(': ')',
        }
        for c in s:
            if c in match:
                stack.append(c)
            else: 
                if not stack or match[stack.pop()] != c:
                    return False
        return not stack

每日温度

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用0来代替。

例如，给定一个列表temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，输出应该是[1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温列表长度的范围是[1, 30000]。每个气温的值的均为华氏度，都是在[30, 100]范围内的整数。

class Solution(object):
    def dailyTemperatures(self, T):
        """
        :type T: List[int]
        :rtype: List[int]
        """
        stack = []
        result = [0] * len(T)
        for i, temp in enumerate(T):
            while stack and T[stack[-1]] < temp:
                result[stack.pop()] = i - stack[-1]
            stack.append(i)
        return result

逆波兰表达式求值

根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如( 1 + 2 ) * ( 3 + 4 )。
该算式的逆波兰表达式写法为( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        opts = {
            '+': lambda x, y: x + y,
            '-': lambda x, y: y - x,
            '*': lambda x, y: x * y,
            '/': lambda x, y: int( y * 1.0 / x )
        }
        stack = []
        for c in tokens:
            if c in opts:
                stack.append(opts[c](stack.pop(),stack.pop()))
            else:
                stack.append(int(c))
        return stack[-1]

深度优先搜索

查找从根结点到目标结点的路径时，结点的处理和添加完全相反的顺序，后进先出，这就是DFS中使用栈的原因。

模板一递归

def neighbors(cur):
    return []


def DFS(cur, target, visited):
    if cur == target:
        return True
    for next_node in neighbors(cur):
        if next_node not in visited:
            visited.add(next_node)
            if DFS(next_node, target, visited):
                return True

    return False

当我们递归地实现DFS时，似乎不需要使用任何栈。
但实际上，我们使用的是由系统提供的隐式栈，也称为调用栈（Call Stack）。
在最坏的情况下，维护系统栈需要O(h)，其中h是DFS的最大深度。

岛屿数量

一个由’1’（陆地）和’0’（水）组成的的二维网格，计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，可以假设该网格的四条边均被水包围。

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0
        rows = len(grid)
        cols = len(grid[0])
        islands = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    islands += 1
                    self.set_island(r, c, grid)
        return islands
    
    def set_island(self, row, col, grid):
        if row >= len(grid) or row < 0 or col >= len(grid[0]) or col < 0:
            return
        if grid[row][col] == '0':
            return
        grid[row][col] = '0'
        self.set_island(row + 1, col, grid)
        self.set_island(row - 1, col, grid)
        self.set_island(row, col + 1, grid)
        self.set_island(row, col - 1, grid)

克隆图

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。

图中的每个节点都包含它的值val（int）和其邻居的列表（list[Node]）。

>>>> 传送门 <<<<

class Node(object):
    def __init__(self, val=0, neighbors=[]):
        self.val = val
        self.neighbors = neighbors


class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return None
        
        cloned = Node(node.val, neighbors=[])
        stack = [node]
        mapping = { node: cloned }
        while stack:
            node = stack.pop()
            cloned_node = mapping[node]
            for neighbor in node.neighbors:
                if neighbor not in mapping:
                    cloned_neighbor = Node(neighbor.val, neighbors=[])
                    mapping[neighbor] = cloned_neighbor
                    stack.append(neighbor)
                else:
                    cloned_neighbor = mapping[neighbor]
                cloned_node.neighbors.append(cloned_neighbor)
        return cloned

目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

>>>> 传送门 <<<<

思路一，递归：
使用递归，枚举出所有可能出现的情况，在处理到i个的数的时候，我们可以选择将它添加或者减除。当处理完nums列表时，计算出所有数的和，和目标数S进行判断。添加一个字典d，用于存储递归时出现的情况，d的key是（current，i），value是从起，到最后一个数，初始值是current时，目标值是S时，所能找到的所有的方法使得最后的数值等于S。

思路二， 01背包：
将这个数组nums看做成两部分，使用+的集合x，和使用-的集合y，则有sum(x) + sum(y) = sum(nums)，而且sum(x) - sum(y) = S，
所以sum(x) = (sum(nums) + S) // 2。就可以看成，已知一个数组，求有多少种方法，将容量为sum(x)的背包填满的问题了。

dp[0]为什么默认为1，因为当背包容量为0时，不需要任何操作就可以填满背包，可行解为1。

class Solution(object):
    # 递归
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        def dfs(current, i, d):
            if i < len(nums) and (current, i) not in d:
                d[(current, i)] = dfs(current + nums[i], i + 1, d) + dfs(current - nums[i], i + 1, d)
            return d.get((current, i), int(current == S))
        return dfs(0, 0, {})

    # 01背包
    def findTargetSumWays_2(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        if sum(nums) < S or (sum(nums) + S ) % 2 == 1:
            return 0
        half = (sum(nums) + S) // 2
        dp = [1] + [0 for _ in range(half)]
        for num in nums:
            for i in range(half, num - 1, -1):
                # i代表背包容量
                # i - num 代表将num放进背包
                dp[i] += dp[i - num]
        return dp[half]

模板二栈

显式的栈。

def neighbors(cur):
    return []


def DFS(root, target):
    visited = set()
    # add root to stack
    stack = [root]
    while stack:
        cur = stack.pop()
        if cur == target:
            return True
        for node in neighbors(cur):
            if node not in visited:
                stack.append(node)
                visited.add(node)
    return 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 inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        result = []
        while root:
            stack.append(root)
            root = root.left
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.right:
                node = node.right
                while node:
                    stack.append(node)
                    node = node.left
        return result

练习

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，可以认为原始数据不包含数字，所有的数字只表示重复的次数k，例如不会出现像3a或2[4]的输入。

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ''
        stack = []
        result = ''
        multi = 0
        for c in s:
            if c == '[':
                stack.append((multi, result))
                result = ''
                multi = 0
            elif c == ']':
                m, res = stack.pop()
                result = res + m * result
            elif '0' <= c <= '9':
                multi = 10 * multi + int(c)
            esle:
                result += c
        return result

图像渲染

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在0到65535之间。

给一个坐标(sr, sc)表示图像渲染开始的像素值（行，列）和一个新的颜色值newColor，重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        old_Color = image[sr][sc]
        if old_Color == newColor:
            return image
        
        rows = len(image)
        cols = len(images)

        def bfs(row, col, image):
            if row >= rows or col >= cols or row < 0 or col < 0:
                return
            if image[row][col] != old_color or image[row][col] == newColor:
                return
            image[row][col] = newColor
            bfs(row + 1, col, image)
            bfs(row - 1, col, image)
            bfs(row, col + 1, image)
            bfs(row, col - 1, image)
        bfs(sr, sc, image)
        return image

钥匙和房间

有 N 个房间，开始时你位于0号房间。每个房间有不同的号码：0，1，2，…，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间i都有一个钥匙列表rooms[i]，每个钥匙rooms[i][j]由[0,1，…，N-1]中的一个整数表示，其中N = rooms.length。钥匙rooms[i][j] = v可以打开编号为v的房间。

最初，除0号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。如果能进入每个房间返回true，否则返回false。

class Solution(object):
    def canVisitAllRooms(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: bool
        """
        seen = [False] * len(rooms)
        seen[0] = True
        stack = [0]
        while stack:
            node = stack.pop()
            for neighbor in rooms[node]:
                if not seen[neighbor]:
                    seen[neighbor] = True
                    stack.append(neighbor)
        return all(seen)

二叉树

树是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。

树里的每一个节点有一个值和一个包含所有子节点的列表。从图的观点来看，树也可视为一个拥有N个节点和N-1条边的一个有向无环图。

二叉树是一种更为典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

节点的深度 - 从树的根节点到该节点的边数
节点的高度 - 该节点和叶子之间最长路径上的边数
树的高度 - 其根节点的高度

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        # 输出前序遍历
        nodes = []

        def preorder(node):
            if not node:
                nodes.append('None')
            else:
                nodes.append(str(node.val))
                preorder(node.left)
                preorder(node.right)

        preorder(self)
        return ', '.join(nodes)

    @classmethod
    def generate(cls, nums):
        """
        :param nums: 前序遍历
        :type nums: list
        :rtype: TreeNode
        """
        nodes = deque(nums)

        def build():
            if not nodes:
                return None
            node = nodes.popleft()
            if node is None:
                return None
            node = TreeNode(node)
            node.left = build()
            node.right = build()
            return node

        return build()

二叉树的遍历

前序遍历
前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树。

中序遍历
中序遍历是先遍历左子树，然后访问根节点，然后遍历右子树。

后序遍历
后序遍历是先遍历左子树，然后遍历右子树，最后访问树的根节点。

前序遍历

class Solution(object):
    # 迭代
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        result = []
        stack = [root]
        while stack:
            node = stack.pop()
            result.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result
    # 递归
    def postorderTraversal2(self, root):
        result = []
        self.dfs(root, result)
        return result
    
    def dfs(self, node, result):
        if not node:    
            return
        result.append(node.val)
        self.dfs(node.left, result)
        self.dfs(node.right, result)

中序遍历

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

    def inorderTraversal2(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        self.dfs(root, result)
        return result
    
    def dfs(self, node, result):
        if not node:
            return
        self.dfs(node.left, result)
        result.append(node.val)
        self.dfs(node.right, result)

后序遍历

import collections

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        result = collections.deque()
        stack = [root]
        while stack:
            node = stack.pop()
            result.appendleft(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return result

    def postorderTraversal2(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        self.dfs(root, result)
        return result
    
    def dfs(self, node, result):
        if not node:
            return
        self.dfs(node.left, result)
        self.dfs(node.right, result)
        result.append(node.val)

二叉树的层序遍历

给一个二叉树，返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        result = []
        nodes = [root]
        while nodes:
            new_nodes = []
            result.append([])
            for node in nodes:
                result[-1].append(node.val)
                if node.left:
                    new_nodes.append(node.left)
                if node.right:
                    new_nodes.append(node.right)
            nodes = new_nodes
        return result

练习

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.dfs(root.left, root.right)
    
    def dfs(self, left_node, right_node):
        if not left_node and not right_node:
            return True
        if not left_node or not right_node:
            return False
        if left_node.val != right_node.val:
            return False
        return self.dfs(left_node.left, right_node.right) and self.dfs(left_node.right, right_node.left)
    
    def isSymmetric2(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        queue = collections.dequeue([(root.left, root.right)])
        while queue:
            l, r = queue.popleft()
            if not l and not r:
                continue
            if not l or not r or l.val != r.val:
                return False
            queue.append((l.left, r.right))
            queue.append((l.right, r.left))

        return True

路径总和

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        sum -= root.val
        if sum == 0 and not root.left and not root.right:
            return True
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if len(inorder) == 0:
            return None
        index = inorder.index(postorder.pop())
        root = TreeNode(inorder[index])

        root.right = self.buildTree(inorder[index + 1:], postorder)
        root.left = self.buildTree(inorder[:index], postorder)

        return root

从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(inorder) == 0:
            return None
        root = TreeNode(preorder[0])
        index = inorder.index(preorder[0])

        root.left = self.buildTree(preorder[1:index + 1], inorder[:index])
        root.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])

        return root
    
    def buildTree2(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        def build(stop=None):
            if not inorder or inorder[-1] == stop:
                return None
            val = preorder.pop()
            root = TreeNode(val)
            root.left = build(val)
            inorder.pop()
            root.right = build(stop)
            return root
            
        
        preorder.reverse()
        inorder.reverse()
        return build()

填充每个节点的下一个右侧节点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

完美二叉树。
一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树，换句话说：树是满的，还是二叉的。

class Node:
  val = int
  left = Node
  right = Node
  next = Node

填充它的每个next指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将next指针设置为NULL。

初始状态下，所有next指针都被设置为NULL。


class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next


class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return None
        level = [root]
        while level and level[0]:
            next_level = []
            prev = None
            for node in level:
                if prev:
                    prev.next = node
                prev = node
                level.append(node.left)
                level.append(node.right)
            level = next_level
        return root
    
    def connect2(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return
        if root.left:
            root.left.next = root.right
            if root.next:
                root.right.next = root.next.left
        self.connect2(root.left)
        self.connect2(root.right)
        return root

填充每个节点的下一个右侧节点指针 II

给定一个二叉树

class Node:
  val = int
  left = Node
  right = Node
  next = Node

填充它的每个next指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将next指针设置为NULL。

初始状态下，所有next指针都被设置为 NULL。


class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next


class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return None
        level = [root]
        while level:
            next_level = []
            prev = None
            for node in level:
                if prev:
                    prev.next = node
                prev = node
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            level = next_level
        return root

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先
对于有根树T的两个结点p、q，最近公共祖先表示为一个结点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）。


class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root or p == root or q == root:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        return left or right

二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

设计一个算法来实现二叉树的序列化与反序列化。这里不限定序列/反序列化算法执行逻辑，只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。


import collections


class Solution(object):
    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        nodes = []

        def preorder(node):
            if not node:
                nodes.append('null')
            else:
                nodes.append(str(node.val))
                preorder(node.left)
                preorder(node.right)
        
        preorder(root)
        return ','.join(nodes)
    
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        nodes = collections.deque(data.split(','))

        def build()
            if not nodes:
                return None
            node = nodes.popleft()
            if node == 'null':
                return None
            node = TreeNode(node)
            node.left = build()
            node.right = build()
            return node

        return build()

二叉搜索树

简介

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：

每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.valid(root, float('-inf'), float('inf'))
    
    def valid(self, node, l, r):
        if not node:
            return True
        if node.val <= l or r <= node.val:
            return False
        return self.valid(node.left, l, node.val) and self.valid(node.right, node.val, r)

二叉搜索树迭代器

实现一个二叉搜索树迭代器。使用二叉搜索树的根节点初始化迭代器。

调用next()将返回二叉搜索树中的下一个最小的数。

class BSTIterator(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack = []
        while root: 
            self.stack.append(root)
            root = root.left


    def next(self):
        """
        @return the next smallest number
        :rtype: int
        """
        node = self.stack()
        result = node.val
        if node.right:
            node = node.right
            while node:
                self.stack.append(node)
                node = node.left
        return result


    def hasNext(self):
        """
        @return whether we have a next smallest number
        :rtype: bool
        """
        return True if self.stack else False

操作

搜索

给定二叉搜索树（BST）的根节点和一个值。需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回NULL。

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root or root.val == val:
            return root
        if root.val < val:
            return self.searchBST(root.right, val)
        else:
            return self.searchBST(root.left, val)
    
    def searchBST2(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root:
            return None
        while root:
            if root.val == val:
                return root
            elif root.val < val:
                root = root.right
            else:
                root = root.left
        return None

插入

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。可以返回任意有效的结果。


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def insertIntoBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        node = TreeNode(val)
        if not root:
            return node
        result = root
        while True:
            if val < root.val:
                if not root.left:
                    root.left = node
                    return result
                root = root.left
            else:
                if not root.right:
                    root.right = node
                    return result
                root = root.right

    def insertIntoBST2(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insertIntoBST2(root.left, val)
        else:
            root.right = self.insertIntoBST2(root.right, val)
        return root

删除

用一个合适的子节点来替换要删除的目标节点。根据其子节点的个数，需考虑以下三种情况：
1. 如果目标节点没有子节点，可以直接移除该目标节点。
2. 如果目标节只有一个子节点，可以用其子节点作为替换。
3. 如果目标节点有两个子节点，要用其中序后继节点或者前驱节点来替换，再删除该目标节点。


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: TreeNode
        :type key: int
        :rtype: TreeNode
        """
        if not root:
            return None
        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        else:
            if not(root.left and root.right):
                root = root.left or root.right
            else:
                next_right = root.right
                while next_right.left:
                    next_right = next_right.left
                root.val = next_right.val
                root.right = self.deleteNode(root.right, root.val)
        return root

小结

二叉搜索树的优点是，即便在最坏的情况下，也允许在O(h)的时间复杂度内执行所有的搜索、插入、删除操作。

有序地存储数据或者需要同时执行搜索、插入、删除等多步操作，二叉搜索树这个数据结构是一个很好的选择。

练习

数据流中的第K大元素

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

KthLargest类需要一个同时接收整数k和整数数组nums的构造器，它包含数据流中的初始元素。每次调用KthLargest.add，返回当前数据流中第K大的元素。

import heapq


class KthLargest(object):

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        heapq.heapfiy(nums)
        while len(nums) > k:
            heapq.heappop(nums)
        self.k = k
        self.nums = nums


    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        if len(self.nums) == self.k and val <= self.nums[0]:
            return self.nums[0]
        heapq.heappush(self.nums, val)
        if len(self.nums) > self.k:
            heapq.heappop(self.nums)
        return self.nums[0]

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if q.val > root.val and p.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        if q.val < root.val and p.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        return root

存在重复元素 III

在整数数组nums中，是否存在两个下标i和j，使得nums[i]和nums[j]的差的绝对值小于等于t ，且满足i和j的差的绝对值也小于等于k。

如果存在则返回true，不存在返回false。


class Solution(object):
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        """
        :type nums: List[int]
        :type k: int
        :type t: int
        :rtype: bool
        """
        if k < 0 or t < 0:
            return False
        buckets = {}
        bucket_size = t + 1
        for i in range(len(nums)):
            num = nums[i] // bucket_size
            if num in buckets:
                return True
            buckets[num] = nums[i]
            if (num - 1) in buckets and abs(buckets[num - 1] - num[i]) <= t:
                return True
            if (num + 1) in buckets and abs(buckets[num + 1] - num[i]) <= t:
                return True
            if i >= k:
                buckets.pop(num[i-k] // bucket_size)
        return False

高度平衡的二叉搜索树

一个高度平衡的二叉搜索树（平衡二叉搜索树）是在插入和删除任何节点之后，可以自动保持其高度最小。也就是说，有N个节点的平衡二叉搜索树，它的高度是logN。并且，每个节点的两个子树的高度不会相差超过1。

一个高度为h的二叉树，节点数为：

一个有N个节点，且高度为h的二叉树，满足：

所以，

判断平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。


class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.balanced(root) != -1
    
    def balanced(self, node):
        if not node:
            return 0
        left = self.balanced(node.left)
        right = self.balanced(node.right)

        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        return self.convert(nums, 0, len(nums) - 1)
    
    def convert(self, nums, left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = self.convert(left, mid - 1)
        root.right = self.convert(mid + 1, right)
        return root

数据结构

目录

链表

单链表

插入

删除

设计链表

双指针

判断是否有环

相交链表

删除倒数第N个节点

经典问题

反转链表

移除链表元素

奇偶链表

回文链表

双链表

插入

删除

小结

时间复杂度对照

练习

合并两个有序的链表

两数相加

旋转链表

队列

循环队列

设计

Python中的队列

广度优先搜索

模板

岛屿数量

打开转盘锁

完全平方数

01 矩阵

栈

经典问题

有效的括号

每日温度

逆波兰表达式求值

深度优先搜索

模板一 递归

岛屿数量

克隆图

目标和

模板二 栈

二叉树的中序遍历

练习

字符串解码

图像渲染

钥匙和房间

二叉树

二叉树的遍历

前序遍历

中序遍历

后序遍历

二叉树的层序遍历

练习

二叉树的最大深度

对称二叉树

路径总和

从中序与后序遍历序列构造二叉树

从前序与中序遍历序列构造二叉树

填充每个节点的下一个右侧节点指针

填充每个节点的下一个右侧节点指针 II

二叉树的最近公共祖先

二叉树的序列化与反序列化

二叉搜索树

简介

验证二叉搜索树

二叉搜索树迭代器

操作

搜索

插入

删除

小结

练习

数据流中的第K大元素

二叉搜索树的最近公共祖先

存在重复元素 III

模板一递归

模板二栈