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

二叉树基础

深度和高度

满二叉树和完全二叉树

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

平衡二叉树

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

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

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

二叉树节点定义

class TreeNode:
	def __init__(self, val, left = None, right = None):
		self.left = left
		self.right = right
		self.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 res
        res = 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 = val
        self.left = left
        self.right = right
        self.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 root
        while len(queue)!=0:
            size = len(queue)
            while size != 0:
                node = queue.popleft()
                if size == 1:
                    node.next = None
                else:
                    node_next = queue[0] # 查看队列出队元素
                    node.next = node_next
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
                size -= 1
        return root