代码随想录算法训练营第13天|二叉树基础知识、递归遍历、迭代遍历、层序遍历、116. 填充每个节点的下一个右侧节点指针

二叉树基础

深度和高度

满二叉树和完全二叉树

满二叉树：除了根节点，每个节点都有两个孩子
完全二叉树：除了最底下的右侧节点可能没填满外，其余每层节点数都达到最大值。

平衡二叉树

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

二叉搜索树和平衡二叉搜索树

二叉搜索树：左节点小于根节点，有节点大于根节点
平衡二叉搜索树：在二叉搜索树的基础上，左右两个子树的高度差的不超过1

二叉树节点定义

class TreeNode:def __init__(self, val, left = None, right = None):self.left = leftself.right = rightself.val = val

前中后序遍历

• 前序遍历：中左右
• 中序遍历：左中右
• 后序遍历：左右中
  

递归遍历

前序递归遍历—144. 二叉树的前序遍历

题目链接：添加链接描述

class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:def dfs(node,res):if node == None:return # 前序：中左右res.append(node.val)dfs(node.left,res)dfs(node.right,res)return resres = dfs(root,[])return res

迭代遍历

前序遍历是中左右，每次先处理的是中间节点，再处理左节点，最后右节点

设计一个栈：先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子

Q：为什么要先加入 右孩子，再加入左孩子呢？

A：因为这样出栈的时候才是中左右的顺序

thon
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:# 前序遍历：中左右# 迭代法：使用栈if not root:return []stack = []vec = []# 先把根节点压入栈中stack.append(root)while len(stack) != 0:# 先弹出栈首node = stack.pop()# 把栈首弹出节点的val记录到vec中vec.append(node.val)# 然后压入此时栈首的左右孩子# 要先压入右孩子，才能先弹出左孩子if node.right:stack.append(node.right)if node.left:stack.append(node.left)return vec

层序遍历

116. 填充每个节点的下一个右侧节点指针

题目链接：

1、题目描述

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，‘#’ 标志着每一层的结束。

2、思路

层序遍历

3、code

"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""
from collections import deque
class Solution:def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':queue = deque()if root != None:queue.append(root)else:return rootwhile len(queue)!=0:size = len(queue)while size != 0:node = queue.popleft()if size == 1:node.next = Noneelse:node_next = queue[0] # 查看队列出队元素node.next = node_nextif node.left is not None:queue.append(node.left)if node.right is not None:queue.append(node.right)size -= 1return root