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

发布于:2025-02-10 ⋅ 阅读:(43) ⋅ 点赞:(0)

一、理论基础

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

文章讲解:代码随想录

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

二、递归遍历 (必须掌握)

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

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

三、迭代遍历 (基础不好的录友,迭代法可以放过)

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
                

四、层序遍历

看完本篇可以一口气刷十道题,试一试, 层序遍历并不难,大家可以很快刷了十道题。

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


网站公告

今日签到

点亮在社区的每一天
去签到