1 二叉树的理论基础
文章链接：代码随想录
视频链接：关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序哔哩哔哩bilibili
1.1 二叉树的种类
-
满二叉树
所有节点处的值都排满了，没有空的
-
完全二叉树
只有在最后一层的时候，从左至右是顺序存储，且空的位置只能在右边，左边不能有空的
-
二叉搜索树
这种就是满足左边数值中满足所有数值都小于根节点数，右边的数值满足所有数值都大于根节点数
-
平衡二叉搜索树
满足二叉搜索树的基本要求后，其左右节点的高度差不超过1
1.2 二叉树的存储方式
链式存储和顺序存储
-
链式存储
这种方式就是相当于之前学的链表一样，每一个值拥有左指针和右指针，最后一层的左右指针指向空位置即可
-
顺序存储
就相当于数组的存储，先存储父节点，然后在存储子节点，一步一步下来
1.3 二叉树的遍历方式
深度遍历和广度遍历
-
深度遍历
这种是先向下遍历；这个分为三种：前序遍历，中序遍历和后续遍历；前序遍历是中左右，中序遍历是左中右，后续遍历是左右中；这个前后的顺序其实是指中节点在哪个位置
-
广度遍历
这种方式就是横着遍历的，就可以使用了
1.4 二叉树的定义方式
这个定义就是需要定义一个值，和左右节点，即指针即可
class TreeNode: def __init__(self,val,left=None,right=None): self.val = val self.left = left self.right = right
2 二叉树的递归遍历
文章链接：代码随想录
视频链接：每次写递归都要靠直觉？ 这次带你学透二叉树的递归遍历！| LeetCode：144.前序遍历，145.后序遍历，94.中序遍历哔哩哔哩bilibili
自己的思路：害，这种题真的就是，一看就会，一做就废
2.1 递归算法的三部曲
-
确定递归函数的参数和返回值
-
确定终止条件
-
确定单层递归的逻辑
2.2 递归的三道题
每次添加的值都是中序的值，其他的就向下遍历
思考:为什么不是左的值和右的值?
因为左和右的值她的下面还有下一层值，无限循环，，，
2.2.1 前序遍历
题目链接：144. 二叉树的前序遍历 - 力扣（LeetCode）
前序的顺序是中左右，所以先添加中序的值，遇到左右继续遍历
# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: result = [] def res(node): if node == None: return result.append(node.val) res(node.left) res(node.right) res(root) return result
2.2.2 中序遍历
题目链接：94. 二叉树的中序遍历 - 力扣（LeetCode）
中序遍历是左中右的顺序，按照这个往下写就行
# 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]: result = [] def dfs(node): if node == None: return dfs(node.left) result.append(node.val) dfs(node.right) dfs(root) return result
2.2.3 后序遍历
题目链接：145. 二叉树的后序遍历 - 力扣（LeetCode）
后序遍历过程中，其内部的结构为左右中
# 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]: result = [] def dfs(node): if node == None: return dfs(node.left) dfs(node.right) result.append(node.val) dfs(root) return result
2.3 本题小结
-
从这道题来理解的话，会发现递归不难，但是自己去写逻辑还是有转不过来的时候
-
主要就是函数调用的时候会很吃力，不知道为什么
3 二叉树的层序遍历思路
文章链接：代码随想录
视频链接：讲透二叉树的层序遍历 | 广度优先搜索 | LeetCode：102.二叉树的层序遍历哔哩哔哩bilibili
3.1 层序遍历的解题思路
-
首先判断整个结尾有没有空，空的话就返回一个空列表
-
对其进行层序遍历，首先是将其值全部存储到队列中，然后一个个弹出，增加现在的位置的值，最终进行值返回
3.2 leetcode102.二叉树的层序遍历
题目链接：102. 二叉树的层序遍历 - 力扣（LeetCode）
3.2.1 队列的方法
import collections # 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if root == None: return [] queue = collections.deque([root]) result =[] while queue: level =[] for _ in range(len(queue)): cur = queue.popleft() level.append(cur.val) if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) result.append(level) return result
3.2.2 递归的方法
import collections # 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if root == None: return [] result =[] def dfs(node,level): if node ==None: return if len(result)==level: result.append([]) result[level].append(node.val) dfs(node.left,level+1) dfs(node.right,level+1) dfs(root,0) return result
3.3 leetcode 107二叉树的层序遍历 II
题目链接：107. 二叉树的层序遍历 II - 力扣（LeetCode）
3.2.1 队列的方法
其实将上一道题进行一个倒序就好了
import collections # 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 levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]: if root == None: return [] queue = collections.deque([root]) result = [] while queue: level = [] for _ in range(len(queue)): cur = queue.popleft() level.append(cur.val) if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) result.append(level) return result[::-1]
3.2.2 递归的方法
import collections # 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 levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]: if root == None: return [] result = [] def dfs(node,level): if node == None: return if len(result) == level: result.append([]) result[level].append(node.val) dfs(node.left,level+1) dfs(node.right,level+1) dfs(root,0) return result[::-1]
4 今日小结
-
怎么说呢，感觉今天的题，学起来很容易，就是一学就会，但是一做就废
-
内容上理解挺容易的，但是感觉因为队列掌握不是很好，其实做就没这么容易了