1.理论
1.1.二叉树
1.1.1.二叉树的遍历
前序(preorder traversal):从根节点开始,先访问当前节点,然后递归地遍历左子树,最后递归地遍历右子树。即“根-左-右”的顺序。
中序遍历(inorder traversal):从根节点开始,先递归地遍历左子树,然后访问当前节点,最后递归地遍历右子树。即“左-根-右”的顺序。
后序遍历(postorder traversal):从根节点开始,先递归地遍历左子树,然后递归地遍历右子树,最后访问当前节点。即“左-右-根”的顺序。
层序遍历(level-order traversal):从根节点开始,按照树的层次顺序,从上到下、从左到右依次访问节点。
遍历顺序: 12345
1.1.2.树的路径和(path sum in binary trees)
树的路径和指的是从树的根节点到叶子节点的路径上所有节点值的和。通常问题会要求找出是否存在这样的路径,或者找出所有满足条件的路径。解决这类问题通常需要使用深度优先搜索(DFS)或广度优先搜索(BFS)等方法。
1.1.3.二叉查找树(binary search trees(BST)
二叉查找树是一种二叉树,其中每个节点的值大于其左子树中的所有节点的值,小于其右子树中的所有节点的值。这种特性使得在BST中进行搜索、插入和删除等操作具有较高的效率。通常,中序遍历BST会得到一个有序的序列。
1.1.4.二叉树转换
二叉树转换指的是将一个二叉树转换为另一个形式的操作。例如,可以将一个有序数组转换为平衡的二叉搜索树,或者将一个二叉搜索树转换为双向链表等。这类问题常常需要根据特定的转换规则来进行设计和实现。
1.2.多叉树遍历
多叉树是一种每个节点可以有多个子节点的树结构。多叉树的遍历方式与二叉树类似,也包括前序、中序、后序和层序遍历。在多叉树中,每个节点的子节点数目不固定,因此在遍历时需要考虑如何处理不同数量的子节点。
真题
简单
94.二叉树的中序遍历
题目:给定一个二叉树的根节点 root
,返回 它的 中序 遍历 。
方法:递归方解法
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result=[]
if root is None:
return result
result +=self.inorderTraversal(root.left)
result.append(root.val)
result +=self.inorderTraversal(root.right)
return result
101.对称二叉树
题目:给你一个二叉树的根节点 root
, 检查它是否轴对称。
题目分析:首先需要检查根节点是否为空,如果为空,返回True,就被认为是对称的。再确定俩边是否为镜像对称,俩个节点都为空被认为是对称的,在比较左右的节点值,如果相同,则返回True,否则False。
方法:迭代法
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
return self.ismrrior(root.left,root.right)
def ismrrior(self,left:TreeNode,right:TreeNode) -> bool:
if not left and not right:
return True
if not left or not right or left.val != right.val:
return False
return self.ismrrior(left.left,right.right) or self.ismrrior(left.right,right.left)
104.二叉树的最大深度
108.将有序数组转换为二叉搜索树
226.翻转二叉树
543.二叉树的直径
590.N叉树的后序遍历
给定一个 n 叉树的根节点 root
,返回 其节点值的 后序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示,每组子节点由空值 null
分隔
中等
98.验证二叉搜索树
102.二叉树的层序遍历
困难
124.二叉树中的最大路径和
参考文献
【1】LeetCode 热题 100 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台
【2】Inorder Traversal of Binary Tree - GeeksforGeeks
【3】Inorder Tree Traversal – Iterative and Recursive | Techie Delight