左神算法系列

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = None


def get_max_width_with_map(node):
    print('The max width of the tree is: ', end=" ")
    if node is not None:
        queue = []
        level_map = {} # 记录每一个节点的所处层
        queue.append(node) # 放入头节点
        level_map[node] = 1 # 设置头节点所在层
        cur_level = 1 # accumulator -> 记录遍历的层数
        cur_level_nodes = 0 # 储存当前层所遍历的节点数
        max_ = 0
        while len(queue) > 0:
            cur_node = queue.pop(0)
            cur_node_level = level_map[cur_node]
            # 分别遍历左右两个节点，并保存其所在层数：当前节点层+1
            if cur_node.left is not None: 
                queue.append(cur_node.left)
                level_map[cur_node.left] = cur_node_level + 1
            if cur_node.right is not None:
                queue.append(cur_node.right)
                level_map[cur_node.right] = cur_node_level + 1
            
            # 判断一层是否遍历结束，观察d出的节点是否等于cur_level
            if cur_node_level == cur_level:
                cur_level_nodes += 1
            # 如果不是，则来到新的层了，更新max_
            else:
                max_ = max(max_, cur_level_nodes)
                cur_level += 1 # 更新当前层
                cur_level_nodes = 1 # 重新记录当前层的节点数
        
        max_ = max(max_, cur_level_nodes) # 因为更新max_的机制是在有新层的时候才更新，所以最后一层需要单独更新
        return max_


def get_max_width_no_map(node):
    print('The max width of the tree is: ', end=" ")
    if node is not None:
        queue = []
        queue.append(node)  # 放入头节点
        curEnd = node # 记录当前层的最右节点
        nextEnd = None # 记录下一层的最右节点
        cur_level_nodes = 0  # 储存当前层所遍历的节点数
        max_ = 0
        while len(queue) > 0:
            cur_node = queue.pop(0)
            # 分别遍历左右两个节点，并且更新下一层最右节点
            if cur_node.left is not None:
                queue.append(cur_node.left)
                nextEnd = cur_node.left 
            if cur_node.right is not None:
                queue.append(cur_node.right)
                nextEnd = cur_node.right
            cur_level_nodes += 1
            # 判断一层是否遍历结束，观察当前节点是否为当前层最右节点
            if cur_node == curEnd:
                max_ = max(max_, cur_level_nodes)
                cur_level_nodes = 0
                curEnd = nextEnd
        # 因为当前层结束时直接更新max_,而不是新层出现时再更新，所以最后不需要更新max
        return max_

套路题一：树的最大宽度

        1. 层序遍历，从而计算每一层的节点数(cur_level_nodes)，并且记录到目前层为止的最大值(max_)

        2. 层序遍历需要使用queue，但需要知道访问到的节点是否是当前层的最右节点，需要额外的变量存储信息

                1）使用HashMap：对于每一个节点，将以节点为key，所处层数为value的pair加入HashMap，并且使用一个变量cur_level记录目前所处层，这样就可以在d出时判断当前层是否结束遍历，如果没结束，则累计cur_level_nodes，如果结束了，则将cur_level + 1并且重置cur_level_nodes

                2) 不使用HashMap：我们需要采用另一种方案来判断是否当前层遍历结束，引入两个新变量curEnd和nextEnd来记录这个信息。在层序遍历时始终更新nextEnd来记录下一层的最右节点，每次d出的节点为当前节点，如果当前节点与当前最右节点一致，那么就已经达到最右，需要更新max_同时重置cur_level_nodes和curEnd

** 两种方法都是采用了一种信息传递的模式来记录是否到达当前层的末尾，前一种用hashMap记录，后一种简单的用指针记录

       3. 需要对变量的初始值进行考虑并且对max_的更新时刻理解很重要，第一种方法是在节点d出后，有新层才更新，所以最后一层的max_需要单独更新，而第二种方法则是在当前层结束时就更新max_，所以无需再return前单独更新max_