В этой статье в основном кратко описаны общие методы, используемые для решения задач типа двоичного дерева в leetcode.Каждый метод решения проблем анализируется на примерах задач leetcode. Неуместно, добро пожаловать на исправление.
Во-первых, используйте рекурсивный обход для решения проблемы
Ключевым моментом рекурсивного решения проблем бинарного дерева является рассмотрение взаимосвязи между корневым узлом, левым поддеревом и правым поддеревом, а остальная часть работы передается обработке обхода.Основная структура бинарного дерева:
if root == None：
return None
# 前序遍历：do_something
traverseTree(root.left)
# 中序遍历：do_something
traverseTree(root.right)
# 后序遍历：do_something
Тема 1: Глубина бинарного дерева (leetcode)
Идеи:Учитывая связь между глубиной дерева в стволе вопроса и количеством корневых узлов, левых поддеревьев и правых поддеревьев, нетрудно найти связь:树的深度=max(左子树深度，右子树深度)+1, используя фреймворк, чтобы получить следующий код:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
# 求左子树深度
ldepth = self.maxDepth(root.left)
# 求右子树深度
rdepth = self.maxDepth(root.right)
# 树的深度
depth = max(ldepth,rdepth) + 1
return depth
Тема 2: Диаметр бинарного дерева (leetcode)
Идеи:Путь любого диаметра должен иметь узел, который разделяет путь на левое и правое поддеревья (левое и правое поддеревья могут быть пустыми). Для поддерева с этим узлом в качестве корневого узла длина пути диаметра дерева может быть преобразована в глубину дерева по формуле:树的直径=左子树深度+右子树深度. Таким образом, получается глубина левого и правого поддеревьев всех узлов, и получаются диаметры всех поддеревьев, причем наибольшее из них является диаметром дерева. Как показано ниже:
Глубина левого поддерева выбранного узла равна 3, а глубина правого поддерева выбранного узла также равна 3, поэтому диаметр выбранного поддерева равен 3+3=6.
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
def depth(node):
if not node:
return 0
L = depth(node.left)
R = depth(node.right)
self.ans = max(self.ans,L+R)
return max(L,R)+1
depth(root)
return self.ans
1. Специальная сцена - одновременно проходятся два узла
Одновременный обход двух узлов в основном направлен на решение проблемы одновременной обработки двух узлов.Ключ в том, чтобы подумать о том, какие операции необходимо выполнить между двумя узлами и как пройти два последних дочерних узла. в то же время. Базовая структура выглядит следующим образом:
if root == None:
return True
return self.helper(root.left,root.right)
def helper(self,node1,node2):
if 达到边界条件：
return
# 对两个节点进行某些操作do_something()
self.helper(node1.子节点，node2.子节点)
Тема 3: Симметричное двоичное дерево (leetcode)
Идеи:Одновременный обход двух узлов иногда является важным магическим оружием для решения некоторых специальных задач, таких как симметричное бинарное дерево.Необходимо судить, согласованы ли значения симметричных узлов в каждом слое.Очевидно, что два узла должны быть пройдены одновременно.Поэтому в сигнатуре функции необходимо установить два параметра.Каждый входной параметр и рекурсивный одновременно, этот метод может пройти все два узла определенного отношения один раз.
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None:
return True
return self.helper(root.left,root.right)
def helper(self,node1,node2):
# 若两个节点非空且数值相同，则用递归判断两个节点的子节点是否相同
if node1 != None and node2 != None and node1.val == node2.val:
return self.helper(node1.left,node2.right) and self.helper(node1.right,node2.left)
# 边界条件，若两个节点均为空，则返回True
if node1 == None and node2 == None:
return True
return False
Тема 4: Заполните указатель следующего правого узла (leetcode) каждого узла
Проблема может быть воссоздана через обход, или вы можете пройти разрешение.
Идеи:Этот анализ рекурсивно проходит. Согласно наблюдению необходимо последовательно ассоциировать две вершины одного уровня, поэтому можно рассматривать особый сценарий обхода — обход двух вершин происходит одновременно. Создание вспомогательных функцийconnectTwoNodes, функция получает в качестве входных параметров два узла и выполняет функцию последовательного соединения двух узлов, при этом граничное условие состоит в том, что первый узел пуст. Все узлы могут быть объединены по мере необходимости с помощью рекурсивных вызовов.
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if root == None:
return root
root.next = None
self.connectTwoNodes(root.left,root.right)
return root
# 连接两个节点
def connectTwoNodes(self,firstNode,secondNode):
# 子节点为空，直接返回
if firstNode == None:
return None
firstNode.next = secondNode
secondNode.next = None
# 将第一个节点的左子节点和第一个节点的右子节点连接
self.connectTwoNodes(firstNode.left,firstNode.right)
# 将第一个节点的右子节点和第二个节点的左子节点连接
self.connectTwoNodes(firstNode.right,secondNode.left)
# 将第二个节点的左子节点和第二个节点的右子节点连接
self.connectTwoNodes(secondNode.left,secondNode.right)
return None
2. Специальная сцена - построение бинарного дерева
Добавление и удаление бинарного дерева повлияет на левый и правый указатели узлов бинарного дерева, поэтому необходимо обратить внимание на назначение левого и правого указателей узлов бинарного дерева по сравнению с обходом.
Тема 5: Построение двоичного дерева (leetcode) из последовательностей обхода в прямом и неупорядоченном порядке.
Идеи:В соответствии с характером обхода мы можем знать, что корневой узел бинарного дерева можно определить обходом в прямом порядке, а затем корневой узел бинарного дерева можно разделить на левую часть обхода по порядку, чтобы построить левое поддерево, правая часть для построения правого поддерева и, наконец, рекурсивно строится все двоичное дерево.После завершения построения обратите внимание, что в процессе построения необходимо назначить левый и правый указатели корневого узла.
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if len(preorder) == 0:
return None
# 从前序遍历序列中取出树的根节点
root = TreeNode(preorder[0])
# 根据根节点在中序遍历中的位置划分左子树和右子树
index = inorder.index(preorder[0])
# 递归构建左子树，节点指针赋值
root.left = self.buildTree(preorder[1:index+1],inorder[0:index])
# 递归构建右子树，节点指针赋值
root.right = self.buildTree(preorder[index+1:],inorder[index+1:])
return root
Во-вторых, используйте обход в ширину для решения проблем.
Давайте сначала посмотрим на поиск в ширину (BFS), как показано на следующем рисунке:
BFS обычно реализуется структурой данных очереди, структура выглядит следующим образом:
if root == None：
return None
# 使用队列，实现节点FIFO
lst = []
lst.append(root)
while lst != []:
node = lst.pop(0)
# 遍历,do_something
if node.left != None:
lst.append(node.left)
if node.right != None:
lst.append(node.right)
Но обычно нам нужно знать иерархическую связь каждого узла в процессе решения задачи, а BFS не может различить иерархическую связь каждого узла. Следовательно, необходимо добавить счетчик в процесс обхода BFS для записи количества узлов на каждом уровне, тем самым формируя обход уровня. Рамка выглядит следующим образом:
if root == None：
return None
# 使用队列，实现节点FIFO
lst = []
lst.append(root)
while lst != []:
# 每次到达新行时便计算此行的节点数n
n = len(lst)
for i in range(n):
node = lst.pop(0)
# 遍历,do_something
if node.left != None:
lst.append(node.left)
if node.right != None:
lst.append(node.right)
Тема 6: Обход двоичного дерева по уровням (leetcode)
Идеи:Вы можете перемещаться по раме прямо на верхнем уровне
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
lst = []
ans = []
lst.append(root)
while lst != []:
n = len(lst)
# 每一行新建一个list
ans.append([])
for i in range(n):
node = lst.pop(0)
ans[-1].append(node.val)
if node.left != None:
lst.append(node.left)
if node.right != None:
lst.append(node.right)
return ans
Тема 7: Заполните указатель следующего правого узла (leetcode) для каждого узла
Идеи:В этом вопросе проблема заключается в использовании иерархического обхода для связывания узлов одного слоя до и после процесса обхода.Следует отметить, что за исключением последнего узла каждой строки, остальные узлы связаны со следующим ряд узлов 2-3, 4-5, 5-6, 6-7. Следующее решение также может решить заголовок leetcode-117 «заполнение следующего правого указателя узла II каждого узла». Существует также рекурсивное решение этой проблемы, подробности см. в теме 4.
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if root == None:
return None
lst = []
lst.append(root)
while lst != []:
n = len(lst)
for i in range(n):
node = lst.pop(0)
if node.left != None:
lst.append(node.left)
if node.right != None:
lst.append(node.right)
#若该节点为该行最后一个节点，则无需设置next指针
if i == n-1:
continue
# 串联同一行的下一节点
node.next = lst[0]
return root