代码随想录（截图自参考【1】）
本系列是代码随想录算法训练营的学习笔记之day15，主要记录一下刷题的过程，以及核心知识点和一些值的记录的问题。
- 落下了几天，需要补了。。
代码随想录的资源可以看参考链接【1】。
今日知识点
二叉树基础：
- 二叉树中的几个关键词：结点、度、叶子结点
- 二叉树的两种主要形式包括满二叉树和完全二叉树
满二叉树（完美二叉树）
- 满二叉树只有度为0和度为2的结点；
- 在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
完全二叉树
- 二叉搜索树：有序树，左子树上所有节点的值小于根结点的值，右子树上所有节点的值大于根结点的值；
二叉搜索树
- 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
平衡二叉搜索树
- 二叉树的储存方式：链式存储
链式存储
顺序存储
用数组存储的二叉树如何遍历呢？如果父节点的下标是i，则左孩子是2i+1，右孩子是2i+2；
-
二叉树的遍历方式主要有深度优先遍历和广度优先遍历：
- 深度优先：前序遍历、中序遍历、后序遍历；
- 广度优先：层次遍历
- 其他的更多理论基础可以去看参考链接【2】；
今日题目
今天的题目主要是代码实现二叉树的遍历相关操作基础。
- 二叉树的前序遍历（144）
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/
- 递归法
# 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]:
re = []
def myfun(root):
if root == None:
return
re.append(root.val)
myfun(root.left)
myfun(root.right)
myfun(root)
return re
- 迭代法
# 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]:
if not root:
return []
stack = [root]
re = []
while stack:
node = stack.pop()
re.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return re
- 二叉树的中序遍历（94）
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/
- 递归法
# 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]:
re = []
def traversal(root):
if root==None:
return
traversal(root.left)
re.append(root.val)
traversal(root.right)
traversal(root)
return re
- 迭代法
# 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]:
if not root:
return []
stack = []
re = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
re.append(cur.val)
cur = cur.right
return re
- 二叉树的后序遍历（145）
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/
- 递归法
# 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]:
re = []
def traversal(root):
if root==None:
return
traversal(root.left)
traversal(root.right)
re.append(root.val)
traversal(root)
return re
- 迭代法
# 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 []
stack = [root]
re = []
while stack:
node = stack.pop()
re.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return re[::-1]
思路
- 要牢记我们遍历的时候处理的对象一直是中间结点的值，在合适的“顺序”把结点的值保存到列表中；
- 栈是先入后出的！所以前序遍历的时候先放右结点，再放左结点，这样子出的时候才是先左后右；
- pop函数模拟出栈，append模拟入栈；
- 后序遍历的顺序是左右中，可以在前序遍历的基础上变化出入栈的顺序（出栈之后的结果是中右左），然后最后的时候翻转数组；
二叉树的统一迭代法
上面的几种迭代方式不够统一，比如在前序和后序中，root一开始是入栈的，但是中序开始的时候root不入栈，不方便理解和记忆，代码随想录网站上给出了统一方式的写法，这里直接搬运下，因为今天知识量超了。。得消化消化。
- 前序遍历
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
result = []
st= []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
if node.right: #右
st.append(node.right)
if node.left: #左
st.append(node.left)
st.append(node) #中
st.append(None)
else:
node = st.pop()
result.append(node.val)
return result
- 中序遍历
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
if node.right: #添加右节点（空节点不入栈）
st.append(node.right)
st.append(node) #添加中节点
st.append(None) #中节点访问过，但是还没有处理，加入空节点做为标记。
if node.left: #添加左节点（空节点不入栈）
st.append(node.left)
else: #只有遇到空节点的时候，才将下一个节点放进结果集
node = st.pop() #重新取出栈中元素
result.append(node.val) #加入到结果集
return result
- 后序遍历
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
st = []
if root:
st.append(root)
while st:
node = st.pop()
if node != None:
st.append(node) #中
st.append(None)
if node.right: #右
st.append(node.right)
if node.left: #左
st.append(node.left)
else:
node = st.pop()
result.append(node.val)
return result
二叉树的知识有点多，也有点难记，还得继续努力~
前面缺的几天慢慢补。。先跟上队伍。
参考
【1】代码随想录：https://programmercarl.com/
【2】https://www.bilibili.com/video/BV1Hy4y1t7ij/?spm_id_from=333.337.search-card.all.click&vd_source=878f5382c5ebdd5fc558a620040e965f
【3】https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html#%E8%BF%AD%E4%BB%A3%E6%B3%95%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86
本文由mdnice多平台发布
