一:树
1、树描述的是一个父子关系;有节点;根节点;叶子节点三个相关的概念
2、树的高度;深度;层
3、二叉树:每个节点最多只有两个孩子
4、完全二叉树:除了叶子节点;每个孩子并不要求都为两个孩子(从上到下,从左到右依次填满节点)
5、满二叉树:除了叶子节点;每个节点都有两个孩子
6、二叉树的遍历
(1)前序遍历:根节点-->左孩子-->右孩子
(2)中序遍历:左孩子-->根节点-->右孩子
(3)后序遍历:左孩子-->右孩子-->根节点
7、树在程序设计当中;一般会直接给出树的结构;不会让你去创建一个树
二:刷题
144 后序遍历二叉树
(1)思路就是先将数组转化二二叉树;然后根据后序遍历的特性依次访问左子树;右子树;最后访问根节点
from collections import deque
# 定义二叉树节点的类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 迭代方法将列表转换为二叉树
def build_tree_iterative(nodes):
if not nodes:
return None
root = TreeNode(nodes[0]) # 创建根节点
queue = deque([root]) # 使用队列来追踪节点
index = 1
while queue and index < len(nodes):
node = queue.popleft() # 取出队列中的第一个节点
# 处理左子树
if index < len(nodes) and nodes[index] is not None:
node.left = TreeNode(nodes[index])
queue.append(node.left) # 左子节点加入队列
index += 1
# 处理右子树
if index < len(nodes) and nodes[index] is not None:
node.right = TreeNode(nodes[index])
queue.append(node.right) # 右子节点加入队列
index += 1
return root
# 层序遍历打印二叉树的节点值
def print_tree_level_order(root):
if not root:
print("[]")
return
result = []
queue = deque([root])
while queue:
node = queue.popleft()
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
# 去除结果列表末尾的 None
while result and result[-1] is None:
result.pop()
print(result)
# 示例
nodes = [1, None, 2, 3]
root = build_tree_iterative(nodes)
print_tree_level_order(root)
前序遍历树
from collections import deque
# 定义二叉树节点的类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 迭代方法将列表转换为二叉树
def build_tree_iterative(nodes):
if not nodes:
return None
root = TreeNode(nodes[0]) # 创建根节点
queue = deque([root]) # 使用队列来追踪节点
index = 1
while queue and index < len(nodes):
node = queue.popleft() # 取出队列中的第一个节点
# 处理左子树
if index < len(nodes) and nodes[index] is not None:
node.left = TreeNode(nodes[index])
queue.append(node.left) # 左子节点加入队列
index += 1
# 处理右子树
if index < len(nodes) and nodes[index] is not None:
node.right = TreeNode(nodes[index])
queue.append(node.right) # 右子节点加入队列
index += 1
return root
# 前序遍历打印二叉树的节点值
def print_tree_preorder(root):
if not root:
print("[]")
return
result = []
stack = [root]
while stack:
node = stack.pop()
if node:
result.append(node.val)
stack.append(node.right) # 先右后左
stack.append(node.left) # 左子节点先入栈,确保左子树优先处理
print(result)
# 示例
nodes = [1, None, 2, 3]
root = build_tree_iterative(nodes)
print_tree_preorder(root)
中序遍历二叉树
from collections import deque
# 定义二叉树节点的类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 迭代方法将列表转换为二叉树
def build_tree_iterative(nodes):
if not nodes:
return None
root = TreeNode(nodes[0]) # 创建根节点
queue = deque([root]) # 使用队列来追踪节点
index = 1
while queue and index < len(nodes):
node = queue.popleft() # 取出队列中的第一个节点
# 处理左子树
if index < len(nodes) and nodes[index] is not None:
node.left = TreeNode(nodes[index])
queue.append(node.left) # 左子节点加入队列
index += 1
# 处理右子树
if index < len(nodes) and nodes[index] is not None:
node.right = TreeNode(nodes[index])
queue.append(node.right) # 右子节点加入队列
index += 1
return root
# 中序遍历打印二叉树的节点值
def print_tree_inorder(root):
if not root:
print("[]")
return
result = []
stack = []
current = root
while stack or current:
# 遍历左子树
while current:
stack.append(current)
current = current.left
# 处理当前节点
current = stack.pop()
result.append(current.val)
# 遍历右子树
current = current.right
print(result)
# 示例
nodes = [1, None, 2, 3]
root = build_tree_iterative(nodes)
print_tree_inorder(root)
标签:node,index,None,LeetCode,nodes,root,节点,刷题
From: https://www.cnblogs.com/gsupl/p/18403174