一、理论基础
需要了解 二叉树的种类,存储方式,遍历方式 以及二叉树的定义。文章讲解:代码随想录
1. 二叉树的种类
(1)满二叉树:
如果一棵树只有度为0和度为2的结点,并且度为0的结点在同一层,则这种二叉树为满二叉树。
(2)完全二叉树:底部从左到右连续
在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层(h从1开始),则该层包含 1~ 2^(h-1) 个节点。之前优先级队列其实是一个堆,堆就是一棵完全二叉树,同时保证父子节点的顺序关系。
满二叉树一定是完全二叉树。
(3)二叉搜索树
树有了数值就是二叉搜索树,二叉搜索树是一个有序树。
若左子树不为空,则左子树的所有结点都小于根结点的值;若右子树不为空,则右子树的所有结点都大于根结点的值;它的左右子树也分别为二叉排序树。
(4)平衡二叉搜索树(AVL)
性质:1)是一颗空树;2)或它的左右两个子树的高度差的绝对值不超过1,并且左右两颗子树都是一棵平衡二叉树。
2. 二叉树的存储方式
(1)链式存储:指针,链式存储则是通过指针把分布在各个地址的节点串联一起。
(2)顺序存储:数组,顺序存储的元素在内存是连续分布的。
数组存储树如何进行遍历:如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。
3. 二叉树的遍历方式
(1)深度优先遍历:先往深走,遇到叶子结点再往回走。
- 前序遍历(递归法,迭代法)
- 中序遍历(递归法,迭代法)
- 后序遍历(递归法,迭代法)
(2)广度优先遍历:一层一层去遍历。
层次遍历(迭代法)
4. 二叉树的定义
二叉树的定义 和链表是差不多的,相对于链表 ,二叉树的节点里多了一个指针, 有两个指针,指向左右孩子。
二叉树是一种基础数据结构,在算法面试中都是常客,也是众多数据结构的基石。
本篇我们介绍了二叉树的种类、存储方式、遍历方式以及定义,比较全面的介绍了二叉树各个方面的重点,帮助大家扫一遍基础。
说到二叉树,就不得不说递归,很多同学对递归都是又熟悉又陌生,递归的代码一般很简短,但每次都是一看就会,一写就废。
5. 总结
二、递归遍历 (必须掌握)
二叉树的三种递归遍历掌握其规律后,其实很简单.
1. 整体思路及知识点
(1)确定递归函数的参数及返回值;
(2)确定终止条件;
(3)确定单层递归逻辑。
2. 细节思路
(1)首先,定义一个树结点类,定义一个初始化结点方法,传入self, val, left, right。
(2)在主类和主方法中,传入self,根结点root:首先定义一个空结果集result用于存放遍历过的结点;接下来定义一个深度优先遍历dfs方法,采用前序遍历对传入的根结点进行遍历;前序遍历的顺序是中-->左-->右,所以首先遍历的是根结点,将根结点的值传入结果集中,再遍历左结点,最后遍历左结点;
(3)调用dfs方法,传入给定的根结点,最后返回结果集。
(4)前中序遍历代码基本一致,只有中间结点遍历顺序不同。
3. 代码
(1)前序遍历:
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]:
result = []
def dfs(node):
if node is None:
return
result.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return result
(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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node):
if node is None:
return
dfs(node.left)
dfs(node.right)
res.append(node.val)
dfs(root)
return res
(3)中序遍历:同前序遍历,只需交换中间结点遍历位置。
# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node):
if node is None:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
dfs(root)
return res
三、迭代遍历 (基础不好的录友,迭代法可以放过)
1. 前序遍历/后序遍历
整体思路:
前序遍历的顺序是中左右,但用栈实现时,由于栈的数据结构是先进后出,所以先处理中间结点,存入结果集,并且从栈中弹出,再去遍历右子结点,将其添加进栈中,最后加入左结点,这样栈在弹出的时候就是先出左结点,再出右结点。
后序遍历的顺序是左右中,只需要在前序遍历代码的基础上,先进栈左结点,后进栈右结点,最后反转一下结果集即可。
a. 前序遍历:
class Solution:
def preorderTraversal(self,root:Optional[TreeNode])->List[int]:
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
b. 后序遍历:
# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res[::-1]
2. 中序遍历
整体思路:先遍历左子树,将结点全部加入栈中,一直到左结点为空也就是遍历到左子树的叶子结点;然后将栈顶结点弹出,再将当前待处理的结点的值加入结果集,然后将当前结点的指针移动至右结点;最后返回result。
注意事项:需要一个cur指针来指向当前遍历的结点。
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
res = []
stack = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
四、层序遍历
看完本篇可以一口气刷十道题,试一试, 层序遍历并不难,大家可以很快刷了十道题。文章讲解/视频讲解:代码随想录
题目链接:
- 102.二叉树的层序遍历(opens new window)
- 107.二叉树的层次遍历II(opens new window)
- 199.二叉树的右视图(opens new window)
- 637.二叉树的层平均值(opens new window)
- 429.N叉树的层序遍历(opens new window)
- 515.在每个树行中找最大值(opens new window)
- 116.填充每个节点的下一个右侧节点指针(opens new window)
- 117.填充每个节点的下一个右侧节点指针II(opens new window)
- 104.二叉树的最大深度(opens new window)
- 111.二叉树的最小深度
1. 102.二叉树的层序遍历
(1)双数组法
首先对传入的根结点是否为空进行异常值处理;然后定义存放结果集的数组ans,cur指针指向当前遍历的数组,为其传入根结点。
然后,只要cur不为空就循环遍历,首先定义空数组vals用于存放当前层,空数组nxt用于存放下一层。首先遍历当前层的元素,将当前层的元素加入当前层vals;如果其左孩子不为空,则将左孩子加入下一层,如果右孩子不为空,则将右孩子加入下一层;然后将当前层的指针指向下一层,将当前层的数组添加至结果集。
最后返回结果集。
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
ans = []
cur = [root]
while cur:
vals = []
nxt = []
for node in cur:
vals.append(node.val)
if node.left: nxt.append(node.left)
if node.right: nxt.append(node.right)
cur = nxt
ans.append(vals)
return ans
(2)队列法
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root is None:
return []
res = []
q = deque([root])
while q:
vals = []
for _ in range(len(q)):
node = q.popleft()
vals.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
res.append(vals)
return res
2. 107.二叉树的层序遍历(二)
只需要在102题目中最后输出时反转一下数组即可。
队列法:
class Solution:
def levelOrderBottom(self, root:Optional[TreeNode])->List[List[int]]:
if root is None:
return []
res = []
q = deque([root])
while q:
vals = []
for _ in range(len(q)):
node = q.popleft()
vals.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
res.append(vals)
return res[::-1]
3. 199.二叉树的右视图
层序遍历的时候,判断是否遍历到单层的最后面的元素,如果是,就放进result数组中,随后返回result就可以了。
class TreeNode:
def _init_(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView(self, root: TreeNode)->List[int]:
if root is None:
return []
q = deque([root])
view = []
while q:
length=len(q)
for i in range(length):
node = q.popleft()
if i == length - 1:
view.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return view
4. 637.二叉树的层平均值
本题就是层序遍历的时候把一层求个总和再取一个均值。
class Solution:
def averageOfLevels(self, root:TreeNode)->List[float]:
if root is None:
return []
q = deque([root])
res = []
while q:
length = len(q)
sum = 0
for i in range(length):
node = q.popleft()
sum += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(sum/length)
return res
5. 429.N叉树的层序遍历
这道题依旧是模板题,只不过一个节点有多个孩子了。
class TreeNode:
def _init_(self, val = None, children = None):
self.val = val
self.children = children
class Solution:
def levelOrder(self, root:'Node')->List[List[int]]:
if root is None:
return []
q = deque([root])
res = []
while q:
length = len(q)
vals = []
for i in range(length):
node = q.popleft()
vals.append(node.val)
for child in node.children:
q.append(child)
res.append(vals)
return res
6. 515.在每个树行中找最大值
层序遍历,取每一层的最大值。
class TreeNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def largestValues(self, root:Optional[TreeNode])->List[int]:
if root is None:
return []
q = deque([root])
res = []
while q:
length = len(q)
max_val = float('-inf')
for i in range(length):
node = q.popleft()
max_val = max(max_val, node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
res.append(max_val)
return res
7. 116.填充每个节点的下一个右侧结点指针
本题依然是层序遍历,只不过在单层遍历的时候记录一下本层的头部节点,然后在遍历的时候让前一个节点指向本节点就可以了。
class Node:
def __init__(self, val: int = 0, left: 'Node'=None, right:'Node'=None, next:'Node'=None):
self.val = val
self.left = left
self.right = right
self.next = next
class Solution:
def connect(self, root:'Node')->'Node':
if root is None:
return root
q = deque([root])
while q:
length = len(q)
prev = None
for i in range(length):
node = q.popleft()
if prev: prev.next = node
prev = node
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return root
8. 117.填充每个节点的下一个右侧结点指针(二)
这道题目说是二叉树,但116题目说是完整二叉树,其实没有任何差别,一样的代码一样的逻辑。
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root is None:
return root
q = deque([root])
while q:
length = len(q)
prev = None
for i in range(length):
node = q.popleft()
if prev: prev.next = node
prev = node
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return root
9. 104.二叉树的最大深度
层序遍历的时候,判断是否遍历到单层的最后面的元素,如果是,就放进result数组中,随后返回result就可以了。
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
l_depth = self.maxDepth(root.left)
r_depth = self.maxDepth(root.right)
depth = max(l_depth, r_depth)+1
return depth
10. 111.二叉树的最小深度
相对于 104.二叉树的最大深度 ,本题还也可以使用层序遍历的方式来解决,思路是一样的。
需要注意的是,只有当左右孩子都为空的时候,才说明遍历的最低点了。如果其中一个孩子为空则不是最低点。
注意:在求二叉树的最小深度时,代码的逻辑需要处理叶子节点的情况当某个子树为空时,不可以直接使用该子树的深度为0来计算最小深度,需要在计算最小深度时考虑子树为空的特殊情况。
# 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 minDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
if root.left is None:
return self.minDepth(root.right)+1
if root.right is None:
return self.minDepth(root.left)+1
l_depth = self.minDepth(root.left)
r_depth = self.minDepth(root.right)
depth = min(l_depth,r_depth)+1
return depth