---

7-2 树相关的题目

---

版权声明：以下题目均来自 LeetCode， 仅仅提供跳转到力扣官网的链接，不在本页面出现题目内容，本文章内容禁止商业用途。

目录

小节	位置
7.2.1	二叉树的遍历
7.2.2	二叉树反序列化（还原）
7.2.3	路径问题
7.2.4	验证各种树
7.2.5	二叉查找树
7.2.6	前缀树

7.2.1 二叉树的遍历

序号	题目	题解
①	LeetCode 144.二叉树的前序遍历	题解7.2.1.1.1
②	LeetCode 94.二叉树的中序遍历	题解7.2.1.1.2
③	LeetCode 145.二叉树的后序遍历	题解7.2.1.1.3
④	LeetCode 102.二叉树的层序遍历	题解7.2.1.2.1
⑤	LeetCode 107.二叉树的层序遍历 II	题解7.2.1.2.2
⑥	LeetCode 103.二叉树的锯齿形层序遍历	题解7.2.1.2.3
⑦	LeetCode 104.二叉树的最大深度	题解7.2.1.3
⑧	LeetCode 111.二叉树的最小深度	题解7.2.1.4
⑨	LeetCode 662.二叉树最大宽度	题解7.2.1.5
⑩	LeetCode 199.二叉树的右视图	题解7.2.1.6
⑪	LeetCode 101.对称二叉树	题解7.2.1.7
⑫	LeetCode 226.翻转二叉树	题解7.2.1.8
⑬	LeetCode 116.填充每个节点的下一个右侧节点指针	题解7.2.1.9
⑭	LeetCode 117.填充每个节点的下一个右侧节点指针 II	题解7.2.1.10
⑮	LeetCode 100.相同的树	题解7.2.1.11

7.2.1.1 深度优先遍历-DFS

7.2.1.1.1 二叉树的前序遍历

LeetCode 144.二叉树的前序遍历 | |返回目录7.2.1

思路：前序遍历就是根结点要先遍历到。中-左-右 的顺序

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''1.递归方法'''
        def preorder(root):
            if not root:
                return
            # 根结点在最开始处理
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)

        res =[]
        preorder(root)
        return res

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''2.非递归方法之一'''
        cur = root
        s, res = [], []
        while cur or len(s)>0:
            # 先遍历根结点及其左子树上的每一个子树的根结点
            while cur:
                res.append(cur.val)
                s.append(cur)
                cur = cur.left
            # 左子树部分遍历完之后就可以遍历右边的子树部分了
            cur = s.pop()
            cur = cur.right
        return res

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''2.非递归方法之二'''
        s, res = [], []
        if root:
            s.append(root)
            while len(s) > 0:
                cur = s.pop()
                res.append(cur.val)
                # 注意这里是先将右子结点入栈，再将左子结点入栈
                # 这样出栈的时候，就是左子结点先出栈，右子结点后出栈
                if cur.right :
                    s.append(cur.right)
                if cur.left:
                    s.append(cur.left)
        return res

7.2.1.1.2 二叉树的中序遍历

LeetCode 94.二叉树的中序遍历| | 返回目录7.2.1

思路：前序遍历就是左子结点要先遍历到。左-中-右 的顺序

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''1.递归方法'''
        def inorder(root):
            if not root:
                return
            
            inorder(root.left)
            # 根结点在中间处理
            res.append(root.val)
            inorder(root.right)

        res =[]
        inorder(root)
        return res

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''2.非递归方法'''
        cur = root
        s, res = [], []
        while cur or len(s)>0:
            while cur:
                # 先将结点入栈而不是读取值
                s.append(cur)
                cur = cur.left 
            
            cur = s.pop()
            # 弹出的结点再读取值
            res.append(cur.val)
            cur = cur.right

        return res

7.2.1.1.3 二叉树的后序遍历

LeetCode 145.二叉树的后序遍历 | |返回目录7.2.1

思路：后序就是按照 左-右-中 的顺序

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''1.递归法'''
        def posorder(root):
            if not root:
                return 
            
            posorder(root.left)
            posorder(root.right)
            # 根结点排在最后处理
            res.append(root.val)
        
        res = []
        posorder(root)
        return res

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''2.非递归方法之一'''
        '''按照先序遍历，只不过是右结点先于左结点，构造成：中-右-左，最后逆序：
        得到 左-右-中 的顺序'''
        cur = root
        s, res = [], []
        while cur or len(s)>0:
            while cur:
                res.append(cur.val)
                s.append(cur)
                # 这里就是先处理左右当中的右子结点
                cur = cur.right
            cur = s.pop()
            # 后处理左结点
            cur = cur.left
        # 此时res是 中-右-左 的顺序，再逆序即可
        res.reverse()
        return res

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''2.非递归方法之二'''
        '''按照先序遍历，只不过是右结点先于左结点，构造成：中-右-左，最后逆序：
        得到 左-右-中 的顺序'''
        s, res = [], []
        if root:
            s.append(root)
            while len(s) > 0:
                cur = s.pop()
                res.append(cur.val)
                # 注意这里是先将左子结点入栈，再将右子结点入栈
                # 这样出栈的时候，就是右子结点先出栈，左子结点后出栈
                if cur.left :
                    s.append(cur.left)
                if cur.right:
                    s.append(cur.right)
        res.reverse()
        return res

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        '''2.非递归方法之三'''
        '''不采用逆序的手段，直接按照需要的顺序求结果'''
        pre, cur = None, root
        s, res = [], []
        while cur or len(s)>0:
            while cur:
                s.append(cur)
                cur = cur.left
            
            cur = s.pop()
            # 如果当前结点没有右子结点，或者其右子结点上一轮已经处理过
            # 就说明应该处理当前结点
            if not cur.right or cur.right == pre:
                res.append(cur.val)
                pre = cur
                cur = None
            # 如果不是，说明存在右子结点，且尚未处理过右子结点
            # 就先将当前结点放回栈，先处理其右子结点
            else:
                s.append(cur)
                cur = cur.right

        return res

7.2.1.2 广度优先遍历-BFS

7.2.1.2.1 二叉树的层序遍历

LeetCode 102.二叉树的层序遍历 | | 返回目录7.2.1

思路：一层一层的遍历。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        # q作为临时队列
        q = [root]
        res = []
        while q:
            layer = []
            # N 实际是当前要遍历的层的结点个数
            N = len(q)
            for i in range(N):
                # 模拟队列的处理方法，即先进的先出，
                cur = q.pop(0)
                layer.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            res.append(layer)
        return res

7.2.1.2.2 二叉树的层序遍历 II

LeetCode 107.二叉树的层序遍历 II| | 返回目录7.2.1

思路：普通的层序遍历再逆序。

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        # q作为临时队列
        q = [root]
        res = []
        while q:
            layer = []
            # N 实际是当前要遍历的层的结点个数
            N = len(q)
            for i in range(N):
                # 模拟队列的处理方法，即先进的先出，
                cur = q.pop(0)
                layer.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            res.append(layer)
        res.reverse()
        return res

7.2.1.2.3 二叉树的锯齿形层序遍历

LeetCode 103.二叉树的锯齿形层序遍历 | | 返回目录7.2.1

思路：普通的层序遍历,对于特定的层进行逆序。这个逆序操作可以在遍历完一层之后再做，也可以在遍历的时候就调整方向，手法是多种的。题解中选择遍历完一层之后再对整层做逆序，操作起来简单一些。

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        # q作为临时队列
        q = [root]
        res = []
        L = 0
        while q:
            layer = []
            # N 实际是当前要遍历的层的结点个数
            N = len(q)
            
            for i in range(N):
                # 模拟队列的处理方法，即先进的先出，
                cur = q.pop(0)
                layer.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            if L % 2 == 0:
                res.append(layer)
            else:
                res.append(layer[::-1])
            # 处理完当前层之后，层索引加一
            L += 1

        return res

7.2.1.3 二叉树的最大深度

LeetCode 104.二叉树的最大深度 | | 返回目录7.2.1

思路1：说白了就是求多少层，就可以考虑使用层序遍历的解法。

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        q = [root]
        h = 0
        while q:
            n = len(q)
            h+=1 # 思路很简单，每有一层，就给深度加上1
            for i in range(n):
                cur = q.pop(0)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            
        return h

思路2：如果按照有多深这个角度来理解，使用深度优先遍历也是可以的。采用递归的方法，写起来也简单。

class Solution:
    def maxDepth(self, root):
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1 

7.2.1.4 二叉树的最小深度

LeetCode 111.二叉树的最小深度| | 返回目录7.2.1

思路1：说白了还是在求层数，就可以考虑使用层序遍历的解法，只不过不一定要遍历到最后一层才停止。

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        q, h = [root], 0

        while q :
            n = len(q)
            h+=1
            for i in range(n):
                cur = q.pop(0)
                # 知道终点条件就行，达到此条件，直接可以返回了，不用继续遍历下一层了
                if (not cur.left) and (not cur.right):
                    return h
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
        
        return h

思路2：依然可以使用深度优先遍历的方法。

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        # 递归的结束条件依然是判断当前结点是否是叶子节点
        if not root.left and not root.right:
            return 1
        
        min_depth =  float('inf')
        if root.left: # 如果左子结点存在, 才去算其深度
            min_depth = min(self.minDepth(root.left), min_depth)
        if root.right: # 如果右子结点存在, 才去算其深度
            min_depth = min(self.minDepth(root.right), min_depth)
        
        return min_depth + 1

7.2.1.5 二叉树最大宽度

LeetCode 662.二叉树最大宽度 | | 返回目录7.2.1

思路1：比较直观的方法是求出每一层的宽度，然后求出最大值，这就可以考虑层次优先遍历。
求每一层的宽度时，因其实就是求最右侧的点到最左侧的点，的宽度是多少，
然而，此时要求将中间的null结点也算作有效的点，干脆就对结点进行编号。
编号方式为，假设其在对应的一个满二叉树中的位置索引编号！

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        width = 0

        if not root:
            return width 

        # 初始化根节点和其序号      
        q = [(root,0)]
        while q:
            N = len(q)
            # 计算该层的最大宽度
            width_of_layer = q[-1][1] - q[0][1] + 1
            # 然后更新width
            width = max(width, width_of_layer)
            for i in range(N):
                cur, index = q.pop(0)
                # 对比原始的层序遍历，只是将入队的元素改为了(node, index)而已
                # index是对应满二叉树的位置索引
                if cur.left:
                    q.append((cur.left, 2*index+1))
                if cur.right:
                    q.append((cur.right, 2*index+2))
            
        return width

思路2：也可以使用递归方法采取深度优先的思路，直观上没有层次遍历方法那么容易理解。
说白了也是利用递归的时候，每次深入结点，就改变index，同时对每层设置了一个起始节点的index，固定在那里，便于计算宽度。直观上不太好理解

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # 这个是存储每一层的最左侧结点的index的哈希表
        layerMin = {}
        def dfs(node: Optional[TreeNode], depth: int, index: int) -> int:
            # 递归结束条件为当前结点为空
            if node is None:
                return 0
            if depth not in layerMin:
                layerMin[depth] = index  # 每一层最先访问到的节点会是最左边的节点，即每一层编号的最小值
            return max(index - layerMin[depth] + 1,
                       dfs(node.left, depth + 1, index * 2 + 1),
                       dfs(node.right, depth + 1, index * 2 + 2))
        return dfs(root, 1, 0)

7.2.1.6 二叉树的右视图

LeetCode 199.二叉树的右视图 | | 返回目录7.2.1

思路1：采用层序遍历，每一层只取最右的结点。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        '''1.广度优先遍历'''
        if not root:
            return []
        
        q=[root]
        res = []
        while len(q) > 0:
            N = len(q)
            for i in range(N):
                cur = q.pop(0)
                if i == N-1:
                    res.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
        
        return res

思路2：采用深度优先遍历，按照先序遍历的基础code进行修改，但是要先遍历右子树上的结点；
并且，我们记住已经遍历过的深度，对于每一深度（层）而言，遍历到这一深度时的第一个结点一定是最右侧的结点。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        '''2.深度优先遍历'''
        if not root:
            return []

        # 每一个元素由[结点, 深度]这样的二元数组构成
        cur = [root,0]
        # 用一个哈希表存储已经遍历过的层的序号
        hash_d = {}
        s, res = [], []

        while cur[0] or s:
            while cur[0]:
                cur_node, cur_d = cur[0], cur[1]
                # 如果当前深度还没有遍历，那么该层遇到的第一个结点就一定是最右侧的结点
                if cur_d not in hash_d:
                    res.append(cur_node.val)
                    hash_d[cur_d] = cur_node

                s.append(cur)
                # 记得往右子树的方向更新cur
                cur = [cur_node.right, cur_d+1]

            cur = s.pop()
            cur = [cur[0].left, cur[1]+1]
        return res

7.2.1.7 对称二叉树

LeetCode 101.对称二叉树 | | 返回目录7.2.1

思路1：采用广度优先(层序)遍历，判断各层是否符合对称条件。
注意，这里对称不光是要值相等，还要让位置符合对称的条件

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        '''1.采用广度优先遍历'''
        if not root:
            return True 

        h = 0
        # 同时将结点，和其对应满二叉树的位置索引保存
        q = [(root,0)]

        while q:
            N = len(q)
            h += 1
            layer = []
            for i in range(N):
                cur = q.pop(0)
                node, idx = cur
                layer.append(cur)
                # 同时将结点，和其对应满二叉树的位置索引保存
                if node.left:   
                    q.append((node.left, 2*idx+1))
                if node.right:
                    q.append((node.right, 2*idx+2))
            
            # 判断当前layer是否符合对称条件
            L, R = 0, N-1
            while L <= R:
                left, right = layer[L], layer[R]
                # 要同时判断值是否相等，以及位置是否满足对称关系
                # 这里先求前几层的结点总数
                front_node_cnts = 2**(h-1) - 1
                
                if left[0].val == right[0].val and \
                    left[1]-front_node_cnts  +  right[1]-front_node_cnts == 2**(h-1)-1:
                    # 其中 left[1]-front_node_cnts 和 right[1]-front_node_cnts 代表的是当前结点索引，减去前几层的结点数
                    # 2**(h-1) 是假设当前层是满的情况时，应该有多少个结点
                    L+=1
                    R-=1
                else:
                    # print(left[0].val,right[0].val,left[1],right[1], front_node_cnts, N-1)
                    return False
        return True

思路2：采用深度优先遍历。
注意，这里要注意，判断左右两个结点的值是否相等时，一定要保证这两个结点来自对称的位置，而未必是同一个结点的左右子结点。

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        '''2.采用深度优先遍历'''
        # 根结点本身为空，返回True
        if not root:
            return True 

         # 结点不为空，再来讨论其子树
        def DFS(left, right):
            '''注意: 
            DFS传入的两个结点，是对称位置的两个结点，而不一定是同一个结点的左右子结点 
            只有对树的根结点而言，对称位置的两个结点，刚好是其左右子结点，再往下就不是左右子结点了！
            '''
            if not left and not right:
                # 如果对称位置的结点都为空，满足对称
                return True 
            elif left and not right:
                # 如果左侧结点不为空，右侧结点为空，显然不对称
                return False
            elif not left and right:
                # 如果左侧结点为空，右侧结点不为空，显然不对称
                return False
            else:
                # 如果对称左右位置的结点都不为空，就要讨论两个条件：
                # 1.左右两个结点的值是否相等：
                # 2.左右两个结点下的子树本身是否满足对称条件
                if left.val != right.val:
                    # 左右结点（即对称位置）的值不相等，显然不对称
                    return False
                else:
                    # 一定要注意DFS传入的两个结点，是对称位置的两个结点，而非同一个结点的左右子结点
                    return DFS(left.left, right.right) and DFS(left.right, right.left)
        
        return DFS(root.left, root.right)

7.2.1.8 翻转二叉树

LeetCode 226.翻转二叉树 | | 返回目录7.2.1

思路1：采用深度优先遍历，递归地反转子树。

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        # 先递归处理该结点的左右子树，使其左右子树已经完成反转
        new_left = self.invertTree(root.left)
        new_right = self.invertTree(root.right)

        # 再将其左右子树交换即可
        root.left, root.right = new_right, new_left
        return root

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

LeetCode 116.填充每个节点的下一个右侧节点指针 | | 返回目录7.2.1

思路1：最直接的思路就是采用广度优先遍历，对每一层进行连接即可。

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return root 
        
        q = [root]
        cur = root 
        while q:
            N =len(q)
            pre = None
            for i in range(N):
                cur = q.pop(0)
                # 层内链接
                if pre:
                    pre.next = cur 
                pre = cur 

                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
        return root 

思路2：由于题目中说了这是满二叉树，所以每一层都是满的，每个父节点都有两个子节点。所以也可以利用这一特点来做，即对已经建立起来的next链接做横向移动。

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        
        if not root:
            return root
        # 从根节点开始
        leftmost = root
        while leftmost.left:
            
            # 遍历这一层节点组织成的横向链表，为下一层的节点更新 next 指针
            head = leftmost
            while head:
                # 1.同一个父节点内的左右子结点链接
                head.left.next = head.right
                # 2.将不同父节点之间的下一层右左子结点链接起来
                if head.next:
                    head.right.next = head.next.left
                
                # 在本层内指针向后移动
                head = head.next
            
            # 去下一层的最左的节点
            leftmost = leftmost.left
        
        return root 

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

LeetCode 117.填充每个节点的下一个右侧节点指针 II | | 返回目录7.2.1

思路1：这个题和上一题的唯一区别就是，该题没有明确说明树是【完全二叉树】，但是依然能够用上一题的层次遍历的方法来做。

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root 
        
        q = [root]
        cur = root 
        while q:
            N =len(q)
            pre = None
            for i in range(N):
                cur = q.pop(0)
                if pre:
                    pre.next = cur 
                pre = cur 

                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
        return root 

7.2.1.11 相同的树

LeetCode 100.相同的树 | | 返回目录7.2.1

思路：如果采用深度优先遍历的思路，其实和【对称二叉树】那道题的思路几乎一致。都是对比对应位置的结点的值是否相等，只不过一个是在树的左右两侧寻找，一个是在两棵树之间寻找。
code的基本写法也是很相似的。

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        '''注意：传入的两个结点，是对两个树对应位置的两个结点'''
        # 如果两个结点都是空结点，满足相等
        if not p and not q:
            return True 
        # 如果一个为空一个不为空，显然不相等
        elif not p and q:
            return False 
        # 如果一个为空一个不为空，显然不相等
        elif p and not q:
            return False 
        else:
            # 如果两个结点都不为空，对比值的大小
            if p.val != q.val:
                # 值不想等，显然不符合
                return False 
            else:
                # 值相等的话，再看其左右子树是否满足
                # 传入的两个结点，是对两个树对应位置的两个结点
                return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

7.2.2 二叉树反序列化（还原）

序号	题目	题解
①	LeetCode 105.从前序与中序遍历序列构造二叉树	题解7.2.2.1
②	LeetCode 106.从中序与后序遍历序列构造二叉树	题解7.2.2.2
③	LeetCode 889.根据前序和后序遍历构造二叉树	题解7.2.2.3

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

LeetCode 105.从前序与中序遍历序列构造二叉树 | | 返回目录7.2.2

思路：核心在于，对于每一棵子树范围的结点，它的先序遍历的第一个元素，一定是该子树的根结点，即[ 根结点-[左子树结点]-[右子树结点] ]。而对于中序遍历,根结点能够将左右子树的结点分开，即[ [左子树结点]-根结点-[右子树结点] ] 。
而且该题强调了无重复元素，所以能够根据这两个遍历方式还原出原始二叉树。

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

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:       
    
        def getNode(preorder_start, preorder_end, inorder_start, inorder_end):
            # 如果传入的先序序列的开始索引已经大于了结束索引，就可以停止了
            if preorder_start > preorder_end:
                return None
            
            # 当前考察的先序序列的第一个元素一定是根结点
            root_val = preorder[preorder_start]
            root_node = TreeNode(root_val)
            # 求出该元素在中序序列中的索引（题目中已经说了没有重复元素，所以可以直接在哈希表中找）
            root_inorder_idx = inorder_index[root_val]

            # 根据中序遍历根结点的位置，我们可以将【中序】遍历分成左右两半，分别代表左右两个子树的【中序】序列
            # 注意，这里只是写了两个区域的端点索引
            left_tree_inorder = [inorder_start, root_inorder_idx-1]
            right_tree_inorder = [root_inorder_idx+1, inorder_end]

            # 还可以得到左子树的结点个数：
            left_tree_node_cnts = root_inorder_idx - inorder_start
            # 根据这个数目，来求左右子树的【先序】序列的端点索引
            left_tree_preorder = [preorder_start+1, preorder_start + left_tree_node_cnts]
            right_tree_preorder = [preorder_start + left_tree_node_cnts + 1, preorder_end]

            # 已经知道左右两个子树的，先序和中序的端点索引了，可以调用递归了
            root_node.left = getNode(left_tree_preorder[0], left_tree_preorder[1], left_tree_inorder[0], left_tree_inorder[1])
            root_node.right = getNode(right_tree_preorder[0], right_tree_preorder[1], right_tree_inorder[0], right_tree_inorder[1])

            return root_node
            
        # 用哈希表暂时将中序遍历的索引存储
        inorder_index = {val:i for i,val in enumerate(inorder)}
        N = len(preorder)        
        root = getNode(0,N-1, 0, N-1) 
        return root

简化版代码：

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:       
        if len(preorder) == 0:
            return None 

        # inorder 元素的序号先存起来
        inorder_index = {}
        for i, num in enumerate(inorder):
            inorder_index[num] = i 
        
        
        def buildNode(L1, R1, L2, R2):
            # 递归终止条件
            if L1>R1 or L2>R2:
                return None 

            root_val = preorder[L1]
            root = TreeNode(val=root_val)

            if L1==R1: # 只够组成一个子结点
                return root
        
            # 划分 inorder 列表
            root_index_in = inorder_index[preorder[L1]]
            left_inorder = (L2, root_index_in-1)
            right_inorder = (root_index_in+1,  R2)
            
            # 划分 preorder 列表
            left_w = left_inorder[1]-left_inorder[0]+1
            left_preorder = (L1+1, L1+left_w)
            right_preorder = (L1+left_w+1, R1)

            # 递归调用函数构造左子结点 、右子结点
            root.left = buildNode(left_preorder[0], left_preorder[1], left_inorder[0], left_inorder[1])
            root.right = buildNode(right_preorder[0], right_preorder[1], right_inorder[0], right_inorder[1])

            return root

        return buildNode(0, len(preorder)-1, 0, len(inorder)-1)

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

LeetCode 106.从中序与后序遍历序列构造二叉树| | 返回目录7.2.2

思路：和上一题的思路是一样的，甚至code都只需要改一点点。改动点是：后序遍历的顺序是根结点在最后一个位置，即[ [左子树结点]-[右子树结点]-根结点 ]

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def getNode(postorder_start, postorder_end, inorder_start, inorder_end):
            # 如果传入的后序序列的开始索引已经大于了结束索引，就可以停止了
            if postorder_start > postorder_end:
                return None
            
            # 当前考察的后序序列的【最后一个】元素一定是根结点
            root_val = postorder[postorder_end]
            root_node = TreeNode(root_val)
            # 求出该元素在中序序列中的索引（题目中已经说了没有重复元素，所以可以直接在哈希表中找）
            root_inorder_idx = inorder_index[root_val]

            # 根据中序遍历根结点的位置，我们可以将【中序】遍历分成左右两半，分别代表左右两个子树的【中序】序列
            # 注意，这里只是写了两个区域的端点索引
            left_tree_inorder = [inorder_start, root_inorder_idx-1]
            right_tree_inorder = [root_inorder_idx+1, inorder_end]

            # 还可以得到左子树的结点个数：
            left_tree_node_cnts = root_inorder_idx - inorder_start
            # 根据这个数目，来求左右子树的【后序】序列的端点索引
            left_tree_postorder = [postorder_start, postorder_start + left_tree_node_cnts-1]
            right_tree_postorder = [postorder_start + left_tree_node_cnts, postorder_end-1]

            # 已经知道左右两个子树的，后序和中序的端点索引了，可以调用递归了
            root_node.left = getNode(left_tree_postorder[0], left_tree_postorder[1], left_tree_inorder[0], left_tree_inorder[1])
            root_node.right = getNode(right_tree_postorder[0], right_tree_postorder[1], right_tree_inorder[0], right_tree_inorder[1])

            return root_node
            
        # 用哈希表暂时将中序遍历的索引存储
        inorder_index = {val:i for i,val in enumerate(inorder)}
        N = len(postorder)        
        root = getNode(0,N-1, 0, N-1) 
        return root

简化版代码：

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if len(inorder) == 0:
            return None 
        
        # inorder 元素的序号先存起来
        inorder_index = {val:i for i,val in enumerate(inorder)}

        def buildNode(L1, R1, L2, R2):
            # 递归终止条件
            if L1>R1 or L2>R2:
                return None 
            
            root_val = postorder[R2]
            root_node = TreeNode(root_val)
            
            if L1==R1: # 只够组成一个子结点
                return root_node

            # inorder subset
            root_index_in = inorder_index[root_val]
            left_inorder = (L1, root_index_in-1)
            right_inorder = (root_index_in+1, R1)

            # postorder subset 
            left_w = root_index_in - L1
            left_postorder = (L2, L2+left_w-1)
            right_postorder = (L2+left_w, R2-1)

            # 递归调用函数构造左子结点 、右子结点
            root_node.left = buildNode(left_inorder[0], left_inorder[1], left_postorder[0], left_postorder[1])
            root_node.right = buildNode(right_inorder[0], right_inorder[1], right_postorder[0], right_postorder[1])

            return root_node 

        N = len(postorder)

        return buildNode(0, N-1, 0,N-1)

7.2.2.3 根据前序和后序遍历构造二叉树

LeetCode 889.根据前序和后序遍历构造二叉树 | | 返回目录7.2.2

思路：实际上，只靠先序遍历和后序遍历的结果，并不能唯一确定地还原二叉树的结构。
但是由于题目中说如果存在多个答案，可以返回任何一个，这样该题才能做。
同样是利用上面二题的思路进行code改写即可。

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:

        def getNode(preorder_start, preorder_end, postorder_start, postorder_end):
            
            if preorder_start > preorder_end:
                return None

            # 当前考察的先序序列的第一个元素一定是根结点
            root_val = preorder[preorder_start]
            root_node = TreeNode(root_val)

            # 说明没有子树了，只需要返回一个结点即可
            if preorder_start == preorder_end:
                return root_node
            
            # 如果该条件成立，说明至少存在一个子树
            if preorder_start + 1 <= preorder_end:
                # 如果先序序列的第二个结点，等于后序遍历的倒数第二个结点，又由于结点的值不存在重复的情况
                # 说明只有一棵子树，题目中说如果有多个答案，可以返回其中任何一个，那么就直接将这种情况当作左子树来处理
                if preorder[preorder_start + 1] == postorder[postorder_end-1]:
                    # 求出前序遍历的 左子树的 区间端点索引
                    left_tree_preorder = [preorder_start + 1, preorder_end]
                    # 求出后序遍历的 左子树的 区间端点索引
                    left_tree_postorder = [postorder_start, postorder_end-1]
                    # 将端点值传入递归函数
                    root_node.left = getNode(left_tree_preorder[0], left_tree_preorder[1], left_tree_postorder[0], left_tree_postorder[1])
                else:
                    # 上面的if如果不成立，说明一定同时存在左右两棵子树

                    # 左子树的根结点，就是先序遍历序列的第二个元素
                    left_root = preorder[preorder_start + 1]
                    # 右子树的根结点，就是后序遍历序列的倒数第二个元素
                    right_root = postorder[postorder_end-1]

                     # 求出前序遍历的 左子树和右子树的 区间端点索引
                    left_tree_preorder = [preorder_start + 1, preorder_index[right_root]-1]
                    right_tree_preorder = [preorder_index[right_root], preorder_end]

                    # 求出后序遍历的 左子树和右子树的 区间端点索引
                    left_tree_postorder = [postorder_start, postorder_index[left_root]]
                    right_tree_postorder = [postorder_index[left_root]+1, postorder_end-1]

                    # 将区间端点索引传入递归函数
                    root_node.left = getNode(left_tree_preorder[0], left_tree_preorder[1], left_tree_postorder[0], left_tree_postorder[1])
                    root_node.right = getNode(right_tree_preorder[0], right_tree_preorder[1], right_tree_postorder[0], right_tree_postorder[1])
                
                return root_node

        preorder_index = {val:i for (i,val) in enumerate(preorder)}
        postorder_index = {val:i for (i,val) in enumerate(postorder)}
        N = len(preorder)
        root = getNode(0,N-1, 0, N-1)

        return root

简化版代码如下：

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:

        if len(preorder) == 0:
            return 0 

        # 需要将两个数组的值和索引都存入哈希表
        preorder_index = {val:i for i,val in enumerate(preorder)}
        postorder_index = {val:i for i,val in enumerate(postorder)}

        def buildNode(L1, R1, L2, R2):
            if L1>R1 or L2>R2:
                return None 
            
            # 以先序列表的最前的数作为根结点
            root_val = preorder[L1]
            root_node = TreeNode(val=root_val)

            if L1==R1: # 只够组成一个结点
                return root_node
            
            else:
                # 说明至少有一颗子树
                if preorder[L1+1] == postorder[R2-1]:
                    # 理论上左子树的根结点==理论上右子树的根结点，说明只有一棵树，就把它当做左子树即可
                    left_preorder = (L1+1, R1)
                    left_postorder = (L2, R2-1)
                    root_node.left = buildNode(left_preorder[0], left_preorder[1], left_postorder[0], left_postorder[1])
                else:
                    # 不满足以上的条件说明有两棵树

                    left_root_val = preorder[L1+1]   # 左子树根结点用先序部分剩下的最左侧点
                    right_root_val = postorder[R2-1] # 右子树的根结点用后续部分倒数第二个

                    # 划分 preorder 列表
                    # 这里就会需要用到右子树根结点在 先序中的位置, 才能将先序的左右区分开
                    left_preorder = (L1+1, preorder_index[right_root_val]-1)
                    right_preorder = (preorder_index[right_root_val], R1)

                    # 划分 postorder 列表
                    # 这里就会需要用到左子树的根结点 在后续中的部分, 才能将后序的左右区分开
                    left_postorder = (L2, postorder_index[left_root_val])
                    right_postorder = (postorder_index[left_root_val]+1, R2-1)

                    # 递归调用函数
                    root_node.left = buildNode(left_preorder[0], left_preorder[1], left_postorder[0], left_postorder[1])
                    root_node.right = buildNode(right_preorder[0], right_preorder[1], right_postorder[0], right_postorder[1])
                return root_node 
            
        N = len(preorder)
        root = buildNode(0,N-1, 0, N-1)  
        return root   

7.2.3 路径问题

序号	题目	题解
①	LeetCode 112.路径总和	题解7.2.3.1
①	LeetCode 113.路径总和 II	题解7.2.3.2
③	LeetCode 124.二叉树中的最大路径和	题解7.2.3.3
④	LeetCode 236.二叉树的最近公共祖先	题解7.2.3.4
⑤	LeetCode 257.二叉树的所有路径	题解7.2.3.5
⑥	LeetCode 1104.二叉树寻路	题解7.2.3.6

7.2.3.1 路径总和

LeetCode 112.路径总和 | | 返回目录7.2.3

思路 1：广度优先遍历。每一层的每个结点都计算其累积的路径和，直到计算完最后一层的结点的路径和。

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        '''1.广度优先遍历'''
        if not root:
            return False
        
        #每一个元素是由 (结点, 之前路径上的路径和)
        q = [(root, 0)]

        while q:
            N = len(q)
            for i in range(N):
                node, pathSum = q.pop(0)

                # 如果当前结点已经是叶子结点了，就需要判断一下刚刚它计算得到的路径和
                if not node.left and not node.right and pathSum + node.val == targetSum:
                    return True

                # 如果不是叶子结点，就继续添加下一层
                if node.left:
                    q.append((node.left, pathSum + node.val))
                
                if node.right:
                    q.append((node.right, pathSum + node.val))

        return False

思路 2：深度优先遍历。每深入一个结点，就减去上面已经遍历过的路径上的结点值的和，相当于值看剩下的结点能否满足剩下的和。

'''2.深度优先遍历'''
def DFS(node, restSum):
    if not node:
        return False
    
    # 如果本身就是叶子结点,就看剩下的 restSum 是不是等于结点值
    elif not node.left and not node.right:
        return restSum == node.val
    
    # 如果本身不是叶子结点，就继续向下深入
    # 只要左右子结点中有一条路能满足即可
    else:
        return DFS(node.left, restSum - node.val) or DFS(node.right, restSum - node.val) 

return DFS(root, targetSum)

7.2.3.2 路径总和II

LeetCode 113.路径总和 II | | 返回目录7.2.3

思路 1：和上一题很类似，只不过上一题只是判断是否存在这样的路径，而该题还要确定出这样的路径，难度稍微提升了一点。
如果我们仍使用广度优先搜索，该如何才能在确定这样的路径存在时，知道前面路径上的所有结点是什么呢？
可以考虑用一个哈希表来记住所有结点的父结点。这样的话就能沿着路径反方向遍历完整条路径。
仅需在上一题的code的基础上做一些修改即可。

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        '''1.广度优先遍历'''
        if not root:
            return []

        # 用一个哈希表来存储各个结点的父结点
        hash_father = {root:None}

        def getPath(node):
            path = []
            # 按照哈希表记录的父结点，一直往上找，并将值添加到path中
            while node:
                path.append(node.val)
                node = hash_father[node]
            # 记得要反转一下path才是从上到下的顺序
            path.reverse()
            return path

        #每一个元素是 (结点, 之前路径上的路径和)
        q = [(root, 0)]
        res = []

        while q:
            N = len(q)
            layer = []
            for i in range(N):
                node, pathSum = q.pop(0)
                # 如果当前结点已经是叶子结点了，就需要判断一下刚刚它计算得到的路径和
                if not node.left and not node.right and pathSum + node.val == targetSum:
                    #return True
                    # 调用getPath向上寻找路径，并添加到结果res中
                    res.append(getPath(node))

                # 如果不是叶子结点，就继续添加下一层
                if node.left:
                    q.append((node.left, pathSum + node.val))
                    # 记得更新左子结点的父结点关系
                    hash_father[node.left] = node
                
                if node.right:
                    q.append((node.right, pathSum + node.val))
                    # 记得更新右子结点的父结点关系
                    hash_father[node.right] = node

        return res

思路 2：也可以使用深度优先遍历，在深度优先遍历的过程中，用一个临时数组记住每个结点之前的路径，然后看加上当前结点后是否满足条件。

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        '''2.深度优先遍历'''
        res, path = [], []
        def DFS(node, resSum):
            if not node:
                return 
            # 当前结点不为空，就先将该结点值放入path中
            path.append(node.val)

            # 然后判断当前结点是否是叶子结点
            if not node.left and not node.right:
                # 如果是叶子结点，且当前结点的值刚好等于剩余的sum值，说明该路径满足条件
                if node.val == resSum:
                    # 满足条件的路径, 就往 res 中添加一次
                    res.append(path[:]) # 这里注意要用 path[:]来进行赋值操作，不然的话会进行浅拷贝
            else:
                # 如果当前结点不是叶子结点，就继续向它的子结点进行延伸
                DFS(node.left, resSum-node.val)
                DFS(node.right,  resSum-node.val)
            # 当前结点处理完之后，要记得将当前结点从 path中移除，因为已经要跳出处理该结点的范围了
            path.pop()
                 
        DFS(root, targetSum)

        return res

        return res

7.2.3.3 二叉树中的最大路径和

LeetCode 124.二叉树中的最大路径和| | 返回目录7.2.3

思路：这里的路径并不一定是指的从根结点出发到叶子结点的路径，而是从一个结点到另一个结点的任意路径。
考察二叉树最小的结构，即1个父结点连着两个子结点的情况：
 father
 /   \
left  right
如果我们的路径要经过father结点，那么路径一共就只有以下几种情况：
1.这一部分作为更大路径的子路径：
a. father; b. father-left; c. father-right
2.自己这一部分构成一个路径：
left-father-right

而至于我们要不要经过 father 结点，那就是看上面这4种情况，能否产生更大的路径和，即：经过father点是否对更大的路径的总和有正向增益？

将这个最小结构放入树当中，这里的左右子结点，可以视为左右子树的总贡献；而father结点的贡献，就视为father结点作为某个子结点时的贡献。

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        
        def maxGain(node):
            if not node:
                return 0
            
            # 递归计算左右子节点的最大贡献值
            # 只有在最大贡献值大于 0 时，才会选取对应子节点
            leftGain = max(maxGain(node.left), 0)
            rightGain = max(maxGain(node.right), 0)

            # 因为结点只能在路径序列中至多出现一次
            # 所以对于任一父结点与其左右子结点能够组成的一个子路径分别为：
            # 1.只取父结点入路径; 2.父结点-左子结点; 3.父结点-右子结点
            local_path_gain = max(node.val, node.val+leftGain, node.val+rightGain)

            # 另有一种情况就是 父结点和两个子结点自己组成大路径，不再作为其它大路径的子部分
            global_path_gain = node.val + leftGain + rightGain
            # 如果是这种情况，我们直接将该路径和与总的结果比较，取较大者
            res[0] = max(res[0], global_path_gain)
            
            # 如果希望将父结点和任一子结点作为一个子路径参与大更大的路径中
            # 我们就把这个子路径的最大路径和返回出去即可
            return local_path_gain

        # 题目中给的条件是 -1000 <= Node.val <= 1000
        # 借用列表来作为全局变量
        res =[-1001]
        maxGain(root)
        return res[0]

7.2.3.4 二叉树的最近公共祖先

LeetCode 236.二叉树的最近公共祖先 | | 返回目录7.2.3

思路1： 既然是找公共祖先，比较容易想到的是，上面的题目中 题解7.2.3.2 为了获取路径，将父结点都存入哈希表中的方法。这里确实可以用。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q: 
            return root 

        # 设置一个哈希表来存储结点的父结点
        hash_father = {root:None}

        # 利用DFS先将各个结点和其父结点都存入hash_father
        def DFS(node):
            if not node :
                return 

            if node.left:
                hash_father[node.left] = node 
                DFS(node.left)
            if node.right:
                hash_father[node.right] = node 
                DFS(node.right)
            return 
        DFS(root)

        # 这样对于 p, q 两个node，都能够一直往上追溯回树的根结点root
        # 这个问题就可以看成两个无环链表的相交问题了
        # 为了code简便起见，这里又用哈希表方法来解决相交问题
        hash_p = {}
        while p:
            hash_p[p] = 1
            p = hash_father[p]
        
        while q:
            if q in hash_p:
                return q
            else:
                q = hash_father[q]

        return None 

思路2：也可以用深度优先遍历，递归的方法找。
注意到题目中提示了，p和q互不相等，且一定位于树中，说明一定有公共祖先！
如果最近祖先是根结点，那么说明p和q一个位于左子树，一个位于右子树；
如果最近公共祖先不是根结点，那么要么位于左子树（说明p和q都位于左子树），要么位于右子树（说明p和q都位于右子树）。
这个概念可以递归推导于任一一个范围的子树。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 这个条件很关键, 意思是顺着根结点往下的路径探索, 如果这条路径上 出现p or q, 那么就会返回p or q
        # 如果该条路径上不存在p或者q, 则会返回 None
        if not root or root == p or root == q: 
            return root
        # left的返回值，要么是None（即p和q都不在左子树中），要么是 p 或者q 或其最近公共祖先
        left = self.lowestCommonAncestor(root.left, p, q)
        # right的返回值，要么是None（即p和q都不在右子树中），要么是 p 或者q 或其最近公共祖先
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left: 
            # 如果left是None，则p和q都不在左子树中，则p和q都在右子树中，答案就是right返回值
            return right
        if not right: 
            # 如果right是None，则p和q都不在右子树中，则p和q都在左子树中，答案就是left 返回值
            return left
            
        # 如果上面两个return都没有返回，说明left和right都不为空
        # 那么p和q分别位于 左、右子树中，最近公共祖先就应该是root
        return root

7.2.3.5 二叉树的所有路径

LeetCode 257.二叉树的所有路径 | | 返回目录7.2.3

思路：采用深度优先遍历，这里的code的写法，也应用到上面的【7.2.3.2 路径总和II】同理，该题也可以用上面的那种拿哈希表存储父结点的思路。

class Solution:
    def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        def DFS(node, path):
            if not node:
                return 
            # 进入到该结点的处理环节，就先将该结点放入path中
            path.append(str(node.val))
            # 是叶子结点,说明已经找到一条路径
            if not node.left and not node.right:
                # 往结果中形成一条路径
                res.append('->'.join(path))
            else:
                DFS(node.left, path)
                DFS(node.right, path)
            # 这一层处理完之后，需要将该结点弹出，不然会继续停留在path中
            path.pop()
        
        res, path = [], []
        DFS(root, path)

        return res

7.2.3.6 二叉树寻路

LeetCode 1104.二叉树寻路| | 返回目录7.2.3

思路：只有偶数层的顺序逆序了，所以对于路径中位于偶数层的数字, 它的位置其实并不是对应原始完全二叉树的位置, 对其进行处理即可。

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:

        def get_reverse_location(label, H):
            '''该函数就是对于偶数层的label, 计算其位置对应原始满二叉树的位置的label'''
            start = 2**(H-1) # 第H层的起始结点
            end = 2**H -1  # 第H层的结束结点:
            new_label = end - label + start 
            return new_label


        # 因为后面会使用到label, 所以label的值可能发生变化, 这里先将其原始值保存
        origin_label = label

        '''因为如果当前label是偶数层, 则需要对其进行处理, 处理之后才能得到原始完全二叉树的位置的label'''
        # 计算当前的label是第几层
        H = 1
        while label > 1:
            label = label // 2
            H += 1
        if H % 2 == 0:
            label = get_reverse_location(origin_label, H)
        else:
            label = origin_label
        # 此时label已经得到校正, 是对应的完全二叉树位置的label

        # label修正之后, 我们就先假设在原始完全二叉树中, 去回溯路径。
        res = []
        # 这个循环是从label开始, 依次向上回溯, 直到根结点1
        while label >= 1:
            res.append(label)
            label = label // 2
        res.reverse() # 逆序之后得到从1到label的路径
        
        # print(res)
        # 此时的res路径是假设按照原始满二叉树来向下寻得的路径
        # 再对其中偶数层的数字进行转换即可
        for i in range(len(res)):
            if (i+1) % 2 == 0:
                # 偶数层
                res[i] = get_reverse_location(res[i], i+1)
        
        return res       

7.2.4 验证各种树

序号	题目	题解
①	LeetCode 1361.验证二叉树	题解7.2.4.1
①	LeetCode 98.验证二叉搜索树	题解7.2.4.2
③	LeetCode 958.二叉树的完全性检验	题解7.2.4.3
④	LeetCode 110.平衡二叉树	题解7.2.4.4

7.2.4.1 验证二叉树

LeetCode 1361.验证二叉树 | | 返回目录7.2.4

思路：这个题乍一看可能不知道在说什么，其实给出的两个列表 leftChild 和 rightChild 的元素指的就是 第 i 个结点的左右指向。
示例1中，i=0的结点，左子结点是leftChild[0]->1，右子结点是rightChild[0]->2;
i=1的结点，左子结点是leftChild[1]->-1,表示没有，右子结点是rightChild[1]->-1,表示没有;
i=2的结点，左子结点是leftChild[2]->3，右子结点是rightChild[2]->-1,表示没有;
i=3的结点，左子结点是leftChild[3]->-1,表示没有，右子结点是rightChild[3]->-1,表示没有;
说白了，就是看每个结点的入度（指入的箭头）是否不超过1，且有且只有1个结点入度为0（即根结点），
以及出度（指出的箭头）是否不超过2，（但是此题每个点只会有left和right两个指向，所以这个条件是自然满足的，可以不用考虑）
以及箭头是否为单向的，比如如果 0指向1，但是1也指向0，那明显是不符合的。
比如示例2中，1和2都指向3，导致3的入度为2，就不符合条件了。

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        # 先建立一个入度的统计列表
        indegree = [0]*n
        # 将每个结点的入度数目进行统计
        for i in range(n):
            if leftChild[i] != -1: indegree[leftChild[i]] += 1
            if rightChild[i] != -1: indegree[rightChild[i]] += 1

        # 先判断是否有且只有一个根结点
        root = []
        for i in range(n):
            # 统计入度为0的结点的数目
            if indegree[i] == 0: 
                root.append(i)
            # 如果有发现入度超过 1 的结点，直接返回False
            elif indegree[i] > 1:
                return False
            else:
                pass

        # 要求有且只有一个根结点，否则就不能满足树的条件！
        if len(root) != 1: 
            return False

        # 确定存在根结点之后，来判断
        # 这里采用层次遍历的方法
        res = []
        q = [root[0]]
        while q:
            N = len(q)
            layer = []
            for i in range(N):
                cur_idx = q.pop(0)
                # 检查cur_idx是否已经存在了，
                # 即判断这里cur_idx作为上一层的子结点，是否还指向了上面的层
                if cur_idx in res:
                    return False
                else:
                    layer.append(cur_idx)

                if leftChild[cur_idx] != -1:
                    q.append(leftChild[cur_idx])
                if rightChild[cur_idx] != -1:
                    q.append(rightChild[cur_idx])

            res.extend(layer)

        # 这里的判断是检查连通性，即所有结点都被包含在树中
        return len(res) == n

7.2.4.2 验证二叉搜索树

LeetCode 98.验证二叉搜索树 | | 返回目录7.2.4

思路1 ：二叉搜索树的重要特性，就是如果按中序遍历的话，其结果是一个递增数组！
利用这一点，稍微改动中序遍历的code，就能够实现二叉搜索树的判定

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        cur = root
        res, s = [], []
        while cur or len(s)>0:
            while cur:
                s.append(cur) 
                cur = cur.left
            cur = s.pop()
            # 在原始的中序遍历读值之前，先判断当前值，是否比前一个值大
            # 就多了这么个步骤
            if res:
                if cur.val <= res[-1]:
                    return False
            res.append(cur.val)
            cur = cur.right
        return True

思路2 ：二叉搜索树当中的每个子树，也都是二叉搜索树。
利用这一点，采用深度优先遍历，递归地判定每个子树都满足二叉搜索的条件，
并将子树部分的最大、最小值往上级传递，就能够实现二叉搜索树的判定

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def DFS(node)-> (bool, int, int):
            if not node:
                # 如果是空树，直接就满足条件
                return True, None, None            
            if node.left:
                # 如果左子结点不为空，才往下递归
                left_tree, left_min, left_max = DFS(node.left)
            else:
                # 否则左子树直接就满足二叉搜索的条件,
                # 手动设置为 left_min = node.val，（这样该结点值能作为左部分的最小值向上传递，）
                # left_max = 无穷小，保证该结点值一定满足二叉搜索条件 
                left_tree, left_min, left_max = True, node.val, -float('inf')
            
            if node.right:
                # 如果右子结点不为空，才往下递归
                right_tree, right_min, right_max = DFS(node.right)
            else:
                # 否则右子树直接就满足二叉搜索的条件,
                # 手动设置为 right_max = node.val（这样该结点值能作为右部分的最大值向上传递，）
                # right_min = 无穷大，保证该结点值一定满足二叉搜索条件 
                right_tree, right_min, right_max = True, float('inf'), node.val

            # 判断左右子树是否满足二叉搜索条件，以及当前结点是否满足
            if left_tree and right_tree and left_max < node.val  and node.val < right_min:
                # 左侧最小数，作为该部分子树最小数的代表：min = left_min
                # 右侧最大数，作为该部分子树最大数的代表：max = right_max
                return True, left_min, right_max
            else:
                # 当返回False的时候，后面两个min max值已经没有意义了，可以随便写
                return False, None, None 
        return DFS(root)[0]

7.2.4.3 二叉树的完全性检验

LeetCode 958.二叉树的完全性检验 | | 返回目录7.2.4

思路：完全二叉树的一个性质就是，对于每一个结点，其序号应当与对应的满二叉树的结点序号对应一致，毕竟满二叉树就是一颗特殊的完全二叉树。
求最大宽度的那个例子里，遍历元素的时候，将其序号取到，而且这个序号，恰巧就是按照满二叉树的排列来取的。

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        # 将根节点的序号初始化为0
        q = [(root,0)]
        i = -1
        while q:
            N = len(q)
            for k in range(N):
                cur, index = q.pop(0)
                # 每遍历一个结点，就将其数组排列顺序 i 加上1
                i += 1
                # 比较两个序号是否相等
                if i != index:
                    return False
                # 在队列入队时，同时搭上其在满二叉树中对应位置的序号
                if cur.left:
                    q.append((cur.left, 2*index+1))
                if cur.right:
                    q.append((cur.right, 2*index+2))
        return True

7.2.4.4 平衡二叉树

LeetCode 110.平衡二叉树 | | 返回目录7.2.4

思路1：对于每个结点，其左右子树的高度差不大于1。
所以可以用深度优先遍历，递归的检查每个子树是否平衡。

class Solution:
    # 第一个递归函数是用来求解结点的height
    # 这其实就是【7.2.1.3 二叉树的最大深度】的递归解法
    def height(self, node):
        if not node:
            return 0
        return max(self.height(node.left), self.height(node.right)) + 1

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        # 要判断左右两个子树的高度差是否超过1, 以及左右子树是否都平衡
        return abs(self.height(root.left) - self.height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

思路2：上面的方案1思路是对的，但是在递归使用 isBalanced 函数的时候，对于每一个结点，都要调用一次 height 来求一次该结点的深度，实际上浪费了很多重复计算。
如果在递归的时候，能够不断的把结点的深度往上传递，就不用每次都用height函数去计算了。
因为父结点的深度 就是 子结点的最大深度+1

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:

        def DFS(node):
            if not node:
                return 0, True
            
            elif not node.left and not node.right:
                return 1, True
            
            else:
                # 分别获取左右子结点的最大深度 和 回传状态
                left, left_status = DFS(node.left)
                right, right_status = DFS(node.right)

                # 回传当前结点的最大深度 和 当前子树是否平衡的状态
                return max(left, right) + 1, left_status and right_status and abs(left-right) <= 1

        
        return DFS(root)[1]
    
    '''
    其实这中code写法，和上一题7.2.4.3的思路2的解法是一致的，
    都是在递归的时候，回传一个需要对比的值
    '''

7.2.5 二叉查找树

序号	题目	题解
①	LeetCode 700.二叉搜索树中的搜索	题解7.2.5.1
①	LeetCode 701.二叉搜索树中的插入操作	题解7.2.5.2
③	LeetCode 450.删除二叉搜索树中的节点	题解7.2.5.3
④	LeetCode 230.二叉搜索树中第K小的元素	题解7.2.5.4
⑤	剑指Offer 54.二叉搜索树的第k大节点	题解7.2.5.5
⑥	LeetCode 235.二叉搜索树的最近公共祖先	题解7.2.5.6
⑦	LeetCode 108.将有序数组转换为二叉搜索树	题解7.2.5.7

7.2.5.1 二叉搜索树中的搜索

LeetCode 700.二叉搜索树中的搜索 | | 返回目录7.2.5

思路：较为简单，按照二叉树的性质：
如果当前结点比val大，就往去左子树找；如果当前结点比val小，就去右子树找。
本身就是一种二分查找。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # '''递归'''
        # if not root or root.val == val:
        #     return root
        
        # if val < root.val:
        #     # 在左子树里递归
        #     return self.searchBST(root.left, val)
        # else:
        #     # 在右子树里递归
        #     return self.searchBST(root.right, val) 

        '''迭代'''
        node = root
        while node:
            if val == node.val:
                return node
            elif  val < node.val:
                node = node.left 
            else:
                node = node.right
        return None

7.2.5.2 二叉搜索树中的插入操作

LeetCode 701.二叉搜索树中的插入操作 | | 返回目录7.2.5

思路：示例中给了两个满足条件的解决结果，会发现第二个解决方式，是对原有的树的根结点做了修改，这样操作起来可能会有点复杂；
其实可以尽量保持原来的树不动，将新结点尽可能地插入到树的最后一层或者倒数第二层去。这样能保证上面的结点的关系是不变的。

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # 如果是空树，直接添加
        if not root:
            return TreeNode(val)
        
        pos = root
        # 从根结点开始遍历
        while pos:
            '''因为题目保证输入数据一定与原始二叉树中任一结点的值不同
            所以只存在 大于 和 小于 两种情况， 不存在 等于 的情况
            这里直接考虑新结点安排在某个叶子结点之后'''
            if val < pos.val:
            # 如果待插入的val, 小于当前结点的val, 就应该往左树上安排
                if not pos.left:
                # 如果左子结点为空, 刚好就放在左子结点
                    pos.left = TreeNode(val)
                    break
                else:
                # 如果当前结点的左子结点不为空, 就继续向下遍历
                    pos = pos.left
            else:
                if not pos.right:
                    pos.right = TreeNode(val)
                    break
                else:
                    pos = pos.right
        # 可以看到code中一定是要找到某个点的 左/ 右子结点为空才插入，
        # 即不改变原来的结点的关系
        return root

7.2.5.3 删除二叉搜索树中的节点

LeetCode 450.删除二叉搜索树中的节点| | 返回目录7.2.5

思路：该题的每一个输入都会对应好几种不同的合理的输出，这主要取决于如何处理被删除的结点的子树。
这里选用一种比较简单的思路，即用右子树代替原来的子树部分，然后将原来的左子树整体搬迁的右子树的下面去；。
那么哪个位置合适呢？原来右子树的左下角的那个结点，将原来的左子树作为左下角结点的左子树，一定是合适的；
这是由BST 左 < 中 < 右 的性质决定的，可以在草稿上画一画。

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root    
        ######### 先查找值为 key 的结点 ##############        
        node, father, tag = root, None, ''
        # 在遍历的时候, 同时记录node的父结点, 以便等会儿进行新的链接操作, 如同删除链表结点那般
        while node:
            if key == node.val:
                # 找到该结点, 退出循环
                break
            elif  key < node.val:
                father = node 
                tag = 'left'    # tag=left表示node是父结点的左子结点
                node = node.left 
            else:
                father = node 
                tag = 'right'   # tag=left表示node是父结点的右子结点
                node = node.right
        
        if not node:
            # 没找到key相同的结点, 直接返回
            return root

        ######### 找到了值为 key 的结点 ##############
        '''这里需要注意，若tag=''，说明一上来就找到了该结点，即要删除的是root结点'''          
        if not node.left and not node.right:
            # 当前结点没有子结点, 直接将该结点置空
            if tag == '':        root = None
            elif tag == 'left' : father.left = None 
            else:                father.right = None 
        elif not node.left:
            # 当前结点无左子结点, 但有右子结点, 用右子结点替代当前结点即可
            if tag == '':        root = root.right
            elif tag == 'left' : father.left = node.right 
            else:                father.right = node.right 
        elif not node.right:
            #  当前结点无右子结点, 但有左子结点, 用左子结点替代当前结点即可
            if tag == '':        root = root.left
            elif tag == 'left' : father.left = node.left 
            else:                father.right = node.left 
        else: 
            # 当前结点左右子结点都不为空, 就要来细节处理一下了
            # 本次code选择将该结点的左子树部分全部移动到右子树最下方
            
            left, right = node.left, node.right
            # 在右子树里进行遍历, 直到找到右子树里最下层的左侧结点
            while right.left:
                right = right.left 
            # 根据二叉搜索树的性质, 右子树部分的点的值, 一定是大于左子树部分的点的值
            # 所以这里直接将原来左子树, 接在右侧最下层的左边, 是一定能满足二叉搜索树的性质的
            right.left = left 

            # 用右子树部分替代原有结点
            if tag == '':        root = root.right
            elif tag == 'left' : father.left = node.right 
            else:                father.right = node.right 
        return root 

精简版代码

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root 
        
        tag, father, node = '', None, root
        while node:
            if key == node.val:
                break
            elif key < node.val:
                father = node 
                tag = 'L'
                node = node.left
            else:
                father = node 
                tag = 'R'
                node = node.right 

        if not node:
            # 没有找到key对应的点
            return root 


        def del_node(tag, father, root, new_node):
            if tag == '': 
                # 说明是根结点要删除, 直接对根结点, 即node进行修改
                root = new_node 
            elif tag == 'L': 
                # node 是其父结点的左子结点
                father.left = new_node
            else:
                # node 是其父结点的右子结点
                father.right = new_node

            return root
        
        if not node.left and not node.right:
            new_node = None
        
        elif not node.left and node.right:
            new_node = node.right

        
        elif node.left and not node.right:
            new_node = node.left

        else:
            left, right = node.left, node.right 
            while right.left:
                right = right.left  
            right.left = left 

            new_node = node.right


        return del_node(tag, father, root,  new_node)  
        

7.2.5.4 二叉搜索树中第K小的元素

剑指Offer 54.二叉搜索树的第k大节点| | 返回目录7.2.5
思路：核心思想是 BST 的中序遍历是升序数列。

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        '''1.最简单的思路：先求中序遍历'''
        '''
        # 1.1 递归
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            res.append(node.val)
            inorder(node.right)

        res = []
        inorder(root)
        return res[k-1]

        # 1.2 迭代
        s, res = [], [] 
        cur = root
        while cur or s:
            while cur:
                s.append(cur)
                cur = cur.left 
            cur = s.pop()
            res.append(cur.val)
            cur = cur.right 

        return  res[k-1]
        '''

        '''2.不用完成全部中序遍历，而在遍历的过程中计数'''
        '''
        # 2.1 递归方案
        def inorder(node):
            if not node:
                return 
            inorder(node.left)

            res[0] +=1
            if res[0] == res[1]:
                res.append(node.val)
                return 

            inorder(node.right) 

        # 用res[0]存放计数器, 用res[1]存放目标值k
        res=[0,k]
        inorder(root)
        return res[-1]
        '''
        # 2.2 迭代方案
        s, i = [],0
        cur = root 
        while cur or s:
            while cur:
                s.append(cur)
                cur = cur.left 
            cur= s.pop()
            i+=1
            if i == k:
                return cur.val 
            cur = cur.right 

7.2.5.5 二叉搜索树的第k大节点

剑指Offer 54.二叉搜索树的第k大节点| | 返回目录7.2.5

思路：上一题是求第k小，这一题是求第k大，核心原理是一样的：利用BST的中序遍历。
只不过这里要求第k大的话，稍微改一下中序遍历的code， 即改成 右-中-左 的形式。

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:

        '''1.递归方案'''
        # def DFS(node):
        #     if not node:
        #         return 

        #     DFS(node.right)

        #     res[0]+=1
        #     if res[0] == res[1]:
        #         res.append(node.val)
        #         return

        #     DFS(node.left)
        
        # res = [0, k]
        # DFS(root)
        # return res[-1]
            
        '''2.迭代方案'''
        s, i = [], 0
        cur = root
        while cur or s:
            while cur:
                s.append(cur)
                cur = cur.right
            cur = s.pop()
            i += 1
            if i == k:
                return cur.val 
            cur = cur.left 

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

LeetCode 235.二叉搜索树的最近公共祖先| | 返回目录7.2.5

思路：该题和 【7.2.3.4 二叉树的最近公共祖先】其实一样，所以可以直接用那道题的code；
但是一棵树是二叉搜索树BST时，有其特殊性，所以也有更快一点的方案。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        '''
        # 1.直接使用普通二叉树 最近公共祖先的code [236题]
        if not root or root == p or root == q: 
            return root
        # left的返回值，要么是None（即p和q都不在左子树中），要么是 p 或者q 或其最近公共祖先
        left = self.lowestCommonAncestor(root.left, p, q)
        # right的返回值，要么是None（即p和q都不在右子树中），要么是 p 或者q 或其最近公共祖先
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left: 
            # 如果left是None，则p和q都不在左子树中，则p和q都在右子树中，答案就是right返回值
            return right
        if not right: 
            # 如果right是None，则p和q都不在右子树中，则p和q都在左子树中，答案就是left 返回值
            return left
            
        # 如果上面两个return都没有返回，说明left和right都不为空
        # 那么p和q分别位于 左、右子树中，最近公共祖先就应该是root
        return root
        '''

        # 依据BST自身的特性来做
        if not root or root == p or root == q: 
            return root
        # 如果两个点的值, 都比当前结点的值小, 那就去当前结点的左子树中寻找
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        # 如果两个点的值, 都比当前结点的值大, 那就去当前结点的右子树中寻找
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        # 如果当前结点的值在p和q的值的中间, 那说明当前结点就是最近公共祖先
        else:
            return root

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

LeetCode 108.将有序数组转换为二叉搜索树| | 返回目录7.2.5

思路：BST本身就是利用二分查找思想来构建的树，所以这里直接用二分法。

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        N = len(nums)
        '''二分法的步骤'''
        def Bi(L, R):
            if L > R:
                return None
            M = L + (R-L)//2
            # 每一次将区间 中间的数 作为当前子树的根结点
            node = TreeNode(nums[M])
            # 中点左侧的数放在左子树处理
            node.left = Bi(L,M-1)
            # 中点右侧的数放在右子树处理
            node.right = Bi(M+1, R)

            return node
        
        return Bi(0, N-1) 

7.2.6 前缀树

前缀树即Trie树（发音类似 “try”），也被称为字典树，是一种树形结构。广泛应用于统计和排序大量的字符串（但不仅限于字符串）。它是根据树的路径来得到字符串，能节省存储空间，减少字符串比较，尽快地查询到需要的字符串，所以经常被用于文本词频统计。

距离说明，现有 await, awake, award, awful, awfully 共5个单词（字符串），据此生成的前缀树如下图所示：

可以观察到，对于重叠部分的子串，是可以公用树中的路径的，这样就减少了存储字符串的空间。
对于每一个字符串的结尾字母形成的结点，用绿色高亮表示，意味着从根结点出发的这条路径存在一个对应的字符串的，这样也就能提高查询效率。比如最右侧的路径中，第一个L和最后的Y都是高亮表示，说明该条路径存在以第一个L结尾，和Y结尾的单词。

序号	题目	题解
①	LeetCode 208.实现 Trie (前缀树)	题解7.2.6.1
①	LeetCode 14.最长公共前缀	题解7.2.6.2
③	LeetCode 211.添加与搜索单词 - 数据结构设计	题解7.2.6.3
④	LeetCode 745.前缀和后缀搜索	题解7.2.6.4

7.2.6.1 实现 Trie (前缀树)

LeetCode 208.实现 Trie (前缀树) | | 返回目录7.2.6

思路 1：利用链表结构来实现树，单独设计出存储字符的结点的结构：TrieNode。
这个结点包含两个基本属性，一个是它的子结点，另一个是它是否是结尾结点；
甚至还可以根据需要，增加结点的属性，比如路径权重，作为结尾的次数等等。
所以这个方法，从直观上来说，容易理解和接受。

from collections import defaultdict
class TrieNode(object):
    def __init__(self):
        # 对于每个结点，一定要有子结点
        # 而子结点往往不像二叉树那样一般有左右两个，
        # 所以用一个字典来存储所有子结点
        self.children = defaultdict(TrieNode)
        # 标记当且结点是否是某个字符串的结尾
        self.word_tail = False
        # 有多少个子串经过当前结点的路径
        # self.weight = 0

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        # 从根结点开始遍历
        cur = self.root
        # 按照子结点继续向下延伸路径
        for c in word:
            # 因为children是用的 defaultdict 来构造
            # 所以不用判断cur.children中是否已存在c，如果不存在会默认构造一个TrieNode对象；详细可以参考defaultdict的用法
            cur = cur.children[c]
        # 字符串最后的结点，要记得标记一下结尾
        cur.is_word = True

    def search(self, word: str) -> bool:
        # 从根结点开始遍历
        cur = self.root
        for c in word:
            # 从子结点中尝试取得当前字符
            cur = cur.children.get(c)
            # 如果子结点中没有该字符，说明不存在这样的字符串
            if not cur:
                return False
        # 如果前面的路径都存在，就要看最后的字符是否是一个结尾字符
        # 因为该函数是查找是否存在某个单词，而非查找前缀
        # 所以直接返回最后结点的“结尾状态”
        return cur.is_word

    def startsWith(self, prefix: str) -> bool:
        # 从根结点开始遍历
        cur = self.root
        # 注意这里是查找前缀，而非查找某个单词
        for c in prefix:
            cur = cur.children.get(c)
            if not cur:
                return False
        # 所以最后不用判断是否存在这样的单词，
        # 而是只要有这样的路径（前缀）即可
        return True

思路 2：利用哈希表来实现。
它是通过字典的嵌套来实现，即一个字符作为字典的key，而字典的value是一个新的子字典，里面包含后续的字符作为key的子字典。就是不断地在字典里面新建更深层的字典。
这种方法理解起来没有使用链表那么直观，但是更省内存，速度也更快。

class Trie(object):
    def __init__(self):
        # 初始化就是建立一个空的哈希表/字典
        self.root = {}
    
    def insert(self, word:str)->None:
        # 依然是从根结点开始
        # 这里可以理解为从最外层往里进行深入
        cur = self.root
        for ch in word:
        # 对于每一个来自word的字符，查看它是否已经是当前层的字典的一个key
            if not ch in cur:
            # 如果当前层还没有ch这个key，那么就需要先建立一个以ch为key的子字典
                cur[ch] = {}
            # 进入ch为key的子字典那一层
            cur = cur[ch]
        # 对于最后一层字典的 'nd' 这个key，设置其value为 1，表示是一个word的结尾。
        cur['end'] = 1
    
    def search(self, word:str)->bool:
        cur = self.root
        for ch in word:
            if not ch in cur:
                return False
            cur = cur[ch]
        # 因为该函数是查找是否有一个word，所以要判断符合条件的路径的最后一层字典
        # 是否包含 end 这个key
        return 'end' in cur
    
    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for ch in prefix:
            if not ch in cur:
                return False
            cur  = cur[ch]
        # 因为该函数只需要判断是否存在这样的路径（前缀），所以只要中途不跳出，就一定存在
        return True

7.2.6.2 最长公共前缀

LeetCode 14.最长公共前缀 | | 返回目录7.2.6
思路：找公共前缀，这里比较自然的就想到了前缀树的思路。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        '''使用前缀树的思路'''
        N = len(strs)
        # 如果只有一个单词，那它本身就是自己的公共前缀
        if N == 1:
            return strs[0]

        Trie = {"root":{}}
        # end_flag = "#end" # 该题只是判断前缀，不用查找单词，所以可以不设置结尾标识
        
        common_prefix = ''
        for word in strs:
            cur = Trie["root"]
            for ch in word:
                if not ch in cur:
                # 如果原来没有这样的路径，就需要新建一个
                    cur[ch] = {}
                # 进入ch为key的那一层
                cur = cur[ch]
                
                if 'weight' not in cur:
                # 如果当前层还没有设置过weight参数，说明是第一次到该层，初始化一下weight参数
                    cur['weight'] = 1
                else:
                # 如果当前层已经设置过weight参数，将ch这一层的路径权重加 1
                    cur['weight'] += 1
                # print(ch, cur['weight'])
                #然后判断, 路径权重是否等于word的数目，等于的话才一定是所有word的公共路径
                if cur['weight'] == N:
                    common_prefix += ch
                
            # cur[end_flag] = True
        return common_prefix

7.2.6.1 添加与搜索单词 - 数据结构设计

LeetCode 211.添加与搜索单词 - 数据结构设计 | | 返回目录7.2.6

思路：利用前缀树的思路来解决。

class WordDictionary:

    def __init__(self):
        self.root = {}
        self.end = 'end'


    def addWord(self, word: str) -> None:
        cur = self.root
        for ch in word:
            if not ch in cur:
                cur[ch] = {}
            cur = cur[ch]
        cur[self.end] = True


    def search(self, word: str) -> bool:
        cur = self.root
        # 因为'.'相当于万能符号，所以当'.'存在的时候，要对该层的所有key进行向下的查找
        # 所以不是一个单路径的查找过程，故这里写成递归函数的形式，当某一条路径没有找到的时候，还能跳回上级的出发点
        def recursive(cur, w, index):
            # 递归结束的条件
            # 因为索引是从0开始的，即待查找的的字符索引是从 0 ~ N-1,（N表示word长度）
            # index 为 N 的时候表示遍历完了整个待查找的的字符串
            if index == len(w):
                # 如果要求匹配的是前缀, 到这里可以直接返回 True
                # return True
                # 但是由于匹配的是word，即完成的单词，就涉及到要判断当前路径是否是结尾的情况
                return False if self.end not in cur else True
                

            ch = w[index]
            # 如果不是万能字符，就按照正常处理
            if ch != '.':
                if ch not in cur:
                    return False
                return recursive(cur[ch], w, index+1)

            # 如果当前是万能字符，就需要对该层的每一个key向下进行搜索
            else:
                for key in cur:
                    # 这个条件往往容易忽略, 如果 key ==self.end, 说明该条路线上已经没有元素了
                    # 就不用再顺着这条路往里面递归了
                    if key == self.end:
                        continue
                    if recursive(cur[key], w, index+1):
                        # 如果向下递归的返回值是True, 这里也就返回True
                        return True
                # 遍历了当前层的所有key都没有返回True的话，最后就只好返回False了
                return False

        return recursive(cur, word, 0)

7.2.6.1 前缀和后缀搜索

LeetCode 745.前缀和后缀搜索 | | 返回目录7.2.6

思路：前缀搜索可以用前缀树的思路，那么后缀搜索就是逆序的前缀搜索；
所以可以考虑使用两个前缀树，一个进行前缀存储，另一个逆序前缀（即后缀）存储、

class WordFilter:

    def __init__(self, words: List[str]):
        self.trie_prefix = {}
        self.trie_suff = {}
        self.end = 'end'
        # 调用 insert_list 函数来从words列表构建前缀树和后缀树
        self.insert_list(words)

        # 因为该题的测试输入时，会出现那种反复查找重复的 前缀 prefix, 后缀 suff 的情况
        # 所以我这里为了提速，将查找过的结果，以 “prefix#suff” 为key, 索引值index为value，存入record字典中，
        # 这样之后出现重复的测试输入，就不用再去计算了
        self.record = {}

    def insert_word(self, root, word, index):
        '''具体的如何插入每个单词'''
        cur = root
        for ch in word:
            if not ch in cur:
                # 对于路径上的每一层，要保存其出现在 words列表 中的index
                cur[ch] = {'index':[], }
            cur = cur[ch]
            cur['index'].append(index)
        cur[self.end] = True


    def find_index(self, root, substr):
        '''查找具有子串：substr 的单词的索引'''
        cur = root
        for ch in substr:
            if not ch in cur:
                return -1
            cur = cur[ch]
        return cur['index']


    def insert_list(self, words):        
        for i in range(len(words)):
            self.insert_word(self.trie_prefix, words[i], i)
            self.insert_word(self.trie_suff, words[i][::-1], i)


    def f(self, pref: str, suff: str) -> int:
        # 如果当前的 prefix 和 suff 的组合，在之前没有查询过，就进行以下的查询
        if pref + '#' + suff not in self.record:
            # 在前缀树中查找该前缀的index
            prefix_index = self.find_index(self.trie_prefix, pref)
            # 在后缀树中查找该后缀的index
            suff_index = self.find_index(self.trie_suff, suff[::-1])

            # 如果二者其一没有找到，那就说明该样例不存在
            if prefix_index == -1 or suff_index== -1:
                self.record[pref + '#' + suff] = -1
            else:
            # 如果前后缀都找到各自的 index，那就求它们的交集
                join_index = set(prefix_index) & set(suff_index)
                # 如果交集大于0， 就存下最大的那个 index
                if len(join_index) > 0:
                    self.record[pref + '#' + suff] = max(join_index)
                # 如果不存在交集，说明该样例也不存在，存储 -1 
                else:
                    self.record[pref + '#' + suff] = -1
        
        return self.record[pref + '#' + suff]