<jupyter_start><jupyter_text>[Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/)。二叉树的序列化与反序列化。不限制访问顺序。思路：从编写代码的简洁性考虑，使用递归的前序遍历来实现，令二叉树的存储形式为字串，'null'表示空节点。该题难点在于序列化与反序列化的顺序一定要相对应。在递归中使用一个全局变量来记录当前递归的位置。<jupyter_code>class Codec:
    def __init__(self):
        self.idx = 0

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ['null']

        res = list()
        s = [root]

        while s:
            cur_node = s.pop()
            if cur_node:
                s.append(cur_node.right)    # 用栈实现时，右节点先入栈才能保证先访问左节点
                s.append(cur_node.left)
                res.append(str(cur_node.val))
            else:
                res.append('null')

        return res

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if not data or data == ['null']:
            return None

        if self.idx < len(data):
            if data[self.idx] == 'null':
                self.idx += 1
                return None
            else:
                new_node = TreeNode(int(data[self.idx]))
                self.idx += 1
                new_node.left = self.deserialize(data)
                new_node.right = self.deserialize(data)
                return new_node<jupyter_output><empty_output><jupyter_text>[二叉树序列化转码](https://www.nowcoder.com/practice/fa9da6d8fa0e4cefb7b3927424417d71?tpId=104&tqId=33273&tPage=1&rp=&ru=/ta/2020sangfor-new&qru=/ta/2020sangfor-new/question-ranking)。给定一二叉树的层次遍历的序列化数组，将其转码成前序序列数组，空节点使用''表示。如给定层序序列数组：```[0, 1, 2, 3, , , 4, , 5, 6, ]```，将其转码成```[0, 1, 3, , 5, , , , 2, , 4, 6, , , ]```。思路：首先根据层序序列构建树，然后进行前序遍历。需要注意的是对空节点的处理，因为空节点要输出''。<jupyter_code>import sys


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


def build_tree(level_ord):
    if not level_ord or level_ord[0] == '#':
        return None

    root = TreeNode(level_ord[0])
    idx = 1
    q = [root]
    while q and idx < len(level_ord):
        cur_node = q.pop(0)

        if idx < len(level_ord):
            if level_ord[idx] != '#':
                left_chd = TreeNode(level_ord[idx])
                cur_node.left = left_chd
                q.append(left_chd)
            idx += 1

        if idx < len(level_ord):
            if level_ord[idx] != '#':
                right_chd = TreeNode(level_ord[idx])
                cur_node.right = right_chd
                q.append(right_chd)
            idx += 1

    return root


def preOrd(root):
    if not root:
        print('#')
        return

    s = [root]
    while s:
        vis = s.pop()
        print(vis.val)
        if vis.val == '#':
            continue

        if vis.right:
            s.append(vis.right)
        else:
            s.append(TreeNode('#'))
        if vis.left:
            s.append(vis.left)
        else:
            s.append(TreeNode('#'))


n = int(sys.stdin.readline().strip())
level_ord = list()
for _ in range(n):
    level_ord.append(sys.stdin.readline().strip())

root = build_tree(level_ord)

preOrd(root)<jupyter_output><empty_output><jupyter_text>[Longest Univalue Path](https://leetcode.com/problems/longest-univalue-path/)。给一颗二叉树，找出树中有多少条长度大于$1$的等值路径。路径长度定义为经过边的数目，且路径只能成线段状，不能成放射状。思路：递归，首先对左右分支递归求出左右分支的最长等值路径长度，然后与当前节点比较，再返回最长长度。难点在于该题的路径不限于从上往下的路径。当一个节点与其左右节点值都相等时，可构成一条长度为$2$的等值路径。同时在由低往高累加长度时，需要注意会有断链的情况，断链时需要重新计数。<jupyter_code>def longestUnivaluePath(self, root: TreeNode) -> int:
    res = 0

    def rec(root):
        nonlocal res
        if not root:
            return 0

        len_left_side, len_right_side = rec(root.left), rec(root.right)
        len_left_new = len_right_new = 0    # 断链时的重新计数器

        if root.left and root.left.val == root.val:
            len_left_new = len_left_side+1
        if root.right and root.right.val == root.val:
            len_right_new = len_right_side+1

        res = max(res, len_left_new+len_right_new)

        return max(len_left_new, len_right_new)

    rec(root)
    return res<jupyter_output><empty_output><jupyter_text>[K-th Symbol in Grammar](https://leetcode.com/problems/k-th-symbol-in-grammar/)。从$1$开始计数，第一行的数字是$0$，以后每一行的数字都由上一行生成，$0$变成$01$,$1$变成$10$。求第$n$行第$k$个数字。思路：上一行的每一个数字变成下一行的两个数字，可以画出一颗二叉树。可以观察到左子节点等于父节点，右子节点与父节点相反。如果$T(n,k)$是从根节点一直往左走或者走了偶次右分支生成而来，那么就等于根节点；如果是从根节点走了奇数次右分支生成而来，那么与根节点相反。$T(n,k)$对应的二叉树索引为$2^{n-1}-1+k$，层层往上计算属于右节点的次数即可。<jupyter_code>def kthGrammar(N: int, K: int) -> int:
    if N == 1:
        return 0

    idx = 2**(N-1)-1+K
    res = 0

    while idx > 1:
        if idx % 2 != 0:    # 奇数则说明是右节点
            res = 1-res    # 0，1之间取反
        idx //= 2

    return res<jupyter_output><empty_output><jupyter_text>[Vertical Order Traversal of a Binary Tree](https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/)。假定二叉树的每一个点都有一个坐标，对于任意一个点$(X,Y)$，其左右子节点的坐标分别为：$(X-1,Y-1)$，$(X+1,Y-1)$。使用一竖直扫描线```x=-inf -> x=+inf```，求扫描线经过的节点序列。限制条件，位于同一横坐标的点，优先输出纵坐标大的，同坐标的点，优先输出节点值大的。思路：根节点坐标$(0,0)$，左右子节点坐标分别为：$(-1,-1)$和$(1,-1)$。先层次遍历树，需要记录的是节点的横坐标，把层次遍历的结果记录到一个表中，以横坐标为key。关键在于限制条件，表中不仅需要存储节点值，还需要存储纵坐标，使用嵌套字典实现。<jupyter_code>def verticalTraversal(root: TreeNode):
    if not root:
        return root

    q = [(0, 0, root)]
    tabel = dict()

    while q:
        x, y, node = q.pop(0)
        tabel.setdefault(x, dict())
        tabel[x].setdefault(y, list())
        tabel[x][y].append(node.val)

        if node.left:
            q.append((x-1, y-1, node.left))
        if node.right:
            q.append((x+1, y-1, node.right))

    res = list()
    for x in sorted(tabel.keys()):    # 扫描线
        node_l = list()
        for y in sorted(tabel[x].keys(), reverse=True):    # 根据纵坐标从大到小排列
            node_l.extend(sorted(tabel[x][y]))    # 根据值从小到大排列
        res.append(node_l)

    return res<jupyter_output><empty_output><jupyter_text>[Convert BST to Greater Tree](https://leetcode.com/problems/convert-bst-to-greater-tree/)。给定一棵BST，每个节点加上比自身大的所有节点的值，构成一颗新BST。思路：BST的中序遍历(左根右)是递增序列，改版后的中序遍历(右根左)是递减序列，逐元素累加即可。<jupyter_code>def convertBST(root: TreeNode) -> TreeNode:
    cur_sum = 0
    s = list()
    vis_node = root

    while s or vis_node:
        if vis_node:
            s.append(vis_node)
            vis_node = vis_node.right    # 一路向右
        else:
            vis_node = s.pop()
            cur_sum += vis_node.val
            vis_node.val = cur_sum

            vis_node = vis_node.left

    return root<jupyter_output><empty_output><jupyter_text>[Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/)。为树节点设置三个指针：左右指针与next指针，其中next指针指向同层右节点。思路：层次遍历。<jupyter_code>def connect(root: 'Node') -> 'Node':
    if not root:
        return None

    q = [root]
    while q:
        level_size = len(q)
        for idx in range(level_size):
            vis = q.pop(0)
            if idx == level_size-1:    # 当前层的最后一个节点next置空
                vis.next = None
            else:
                vis.next = q[0]

            if vis.left:
                q.append(vis.left)
            if vis.right:
                q.append(vis.right)

    return root<jupyter_output><empty_output><jupyter_text>[Find Bottom Left Tree Value](https://leetcode.com/problems/find-bottom-left-tree-value/)。给一颗二叉树，找到最后一层最左边的值。思路：层次遍历，保存每一层的首节点。<jupyter_code>def findBottomLeftValue(root: TreeNode) -> int:
    if not root:
        return None

    q = [root]
    res = root.val
    while q:
        level_size = len(q)
        for idx in range(level_size):
            vis_node = q.pop(0)
            if idx == 0:
                res = vis_node.val

            if vis_node.left:
                q.append(vis_node.left)
            if vis_node.right:
                q.append(vis_node.right)

    return res<jupyter_output><empty_output><jupyter_text>[Find Largest Value in Each Tree Row](https://leetcode.com/problems/find-largest-value-in-each-tree-row/)。找出二叉树每一层的最大值。思路：层次遍历，在每层的访问中保存最大值，然后加到res中。<jupyter_code>def largestValues(root: TreeNode):
    res = list()
    if not root:
        return res

    q = [root]
    while q:
        level_size = len(q)
        cur_max = -0x80000000

        for idx in range(level_size):
            cur_node = q.pop(0)
            cur_max = max(cur_max, cur_node.val)

            if cur_node.left:
                q.append(cur_node.left)
            if cur_node.right:
                q.append(cur_node.right)

        res.append(cur_max)

    return res<jupyter_output><empty_output><jupyter_text>[霍夫曼树](https://www.nowcoder.com/practice/e9324e017e3146bab98808e261fc2d94?tpId=104&tqId=33262&tPage=1&rp=&ru=%2Fta%2F2020sangfor-new&qru=%2Fta%2F2020sangfor-new%2Fquestion-ranking)。构建霍夫曼树并按节点顺序输出。思路：构建霍夫曼树本身不难，只是这题的输出要求很奇葩，需要记录原本的节点顺序和构造过程的节点顺序，因此只能使用遍历来做。<jupyter_code>import sys

n = int(sys.stdin.readline().strip())
vals = list(map(int, sys.stdin.readline().strip().split()))


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.par_idx = None    # 父节点索引，单纯考虑输出这么设置


def buildTree(vals):
    nodes = list(map(TreeNode, vals))

    while True:
        min1_idx = None
        min2_idx = None
        need_cnt = 0    # 需要处理的点数
        l = len(nodes)

        for i in range(l):
            if nodes[i].par_idx:    # 跳过以归并的点
                continue

            need_cnt += 1

            # 寻找最小节点与次小节点
            if min1_idx is None:
                min1_idx = i
            elif nodes[i].val < nodes[min1_idx].val:
                min2_idx = min1_idx
                min1_idx = i
            elif min2_idx is None:
                min2_idx = i
            elif nodes[i].val < nodes[min2_idx].val:
                min2_idx = i

        if need_cnt < 2:     # 归并完成
            break

        new_node = TreeNode(nodes[min1_idx].val + nodes[min2_idx].val)
        new_node.left = nodes[min2_idx]
        new_node.right = nodes[min1_idx]
        nodes[min1_idx].par_idx = l
        nodes[min2_idx].par_idx = l
        nodes.append(new_node)

    return nodes


nodes = buildTree(vals)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12690504103165298, 'fraction_numerical': 0.01826885502149277, 'mean_word_length': 2.3129449838187703, 'pattern_counts': {'":': 0, '<': 48, '<?xml version=': 0, '>': 48, 'https://': 10, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '528281', 'license': 'MIT', 'n_tokens_mistral': 4588, 'n_tokens_neox': 4694, 'n_words': 594, 'path': 'Algorithm/Tree/.ipynb_checkpoints/Untitled-checkpoint.ipynb', 'repo_name': 'Daya-Jin/DataStructureAndAlgorithm', 'size': '10236'}