【二叉树】刷题（以递归写法为主）

**二叉树刷题**

二叉树是一种常见的数据结构，广泛应用于算法设计、计算机科学等领域。以下是关于二叉树的一些常见问题及其解决方案。

###1. 二叉树的定义和基本概念二叉树是一棵特殊的树形结构，每个结点最多有两个子结点（左孩子和右孩子）。二叉树的每个结点都有一个值，或者说是数据。二叉树的高度是从根结点到叶结点的最大路径长度。

###2. 二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树中的每个结点的一系列操作。常见的二叉树遍历有前序遍历、中序遍历和后序遍历。

#### 前序遍历前序遍历是指先访问根结点，然后再访问左孩子和右孩子。

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef preorder_traversal(root):
 if root is not None:
 print(root.value) # 访问根结点 preorder_traversal(root.left) # 访问左孩子 preorder_traversal(root.right) # 访问右孩子

def inorder_traversal(root):
 if root is not None:
 inorder_traversal(root.left) # 访问左孩子 print(root.value) # 访问根结点 inorder_traversal(root.right) # 访问右孩子

def postorder_traversal(root):
 if root is not None:
 postorder_traversal(root.left) # 访问左孩子 postorder_traversal(root.right) # 访问右孩子 print(root.value) # 访问根结点

def create_binary_tree():
 root = Node(1)
 root.left = Node(2)
 root.right = Node(3)
 root.left.left = Node(4)
 root.left.right = Node(5)
 return root

class Queue:
 def __init__(self):
 self.items = []

 def enqueue(self, item):
 self.items.append(item)

 def dequeue(self):
 return self.items.pop(0)

def create_binary_tree_iterative():
 queue = Queue()
 root = Node(1)
 queue.enqueue(root)

 while not queue.is_empty():
 node = queue.dequeue()

 if node is None:
 break node.left = Node(2)
 queue.enqueue(node.left)

 node.right = Node(3)
 queue.enqueue(node.right)

 node.left.left = Node(4)
 queue.enqueue(node.left.left)

 node.left.right = Node(5)
 queue.enqueue(node.left.right)

 return root

def find_node(root, target):
 if root is None or root.value == target:
 return root left_result = find_node(root.left, target)
 if left_result is not None:
 return left_result right_result = find_node(root.right, target)
 return right_result

def find_node_iterative(root, target):
 queue = Queue()
 queue.enqueue(root)

 while not queue.is_empty():
 node = queue.dequeue()

 if node is None:
 break if node.value == target:
 return node if node.left is not None:
 queue.enqueue(node.left)

 if node.right is not None:
 queue.enqueue(node.right)

 return None

def delete_node(root, target):
 if root is None or root.value == target:
 return None root.left = delete_node(root.left, target)
 root.right = delete_node(root.right, target)

 return root

def delete_node_iterative(root, target):
 queue = Queue()
 queue.enqueue(root)

 while not queue.is_empty():
 node = queue.dequeue()

 if node is None:
 break if node.value == target:
 # 删除结点的值 node.value = None if node.left is not None:
 queue.enqueue(node.left)

 if node.right is not None:
 queue.enqueue(node.right)

 return root