代码随想录 Day 13 | 【第六章 二叉树】理论基础、递归遍历、迭代遍历、层序遍历

一、理论基础

需要了解 二叉树的种类，存储方式，遍历方式 以及二叉树的定义。

文章讲解：代码随想录

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. 总结

二、递归遍历 （必须掌握）

二叉树的三种递归遍历掌握其规律后，其实很简单.

题目链接/文章讲解/视频讲解：代码随想录

• 144.二叉树的前序遍历(opens new window)
• 145.二叉树的后序遍历(opens new window)
• 94.二叉树的中序遍历

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

三、迭代遍历 （基础不好的录友，迭代法可以放过）

文章讲解： 代码随想录

视频讲解：

• 写出二叉树的非递归遍历很难么？（前序和后序）(opens new window)
• 写出二叉树的非递归遍历很难么？（中序）)

题目链接：

• 144.二叉树的前序遍历(opens new window)
• 94.二叉树的中序遍历(opens new window)
• 145.二叉树的后序遍历(opens new window)

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