当前位置：网站首页>Leetcode107-二叉树的层序遍历II详解

Leetcode107-二叉树的层序遍历II详解

2022-07-25 23:55:00 【白羊by】

往期博客：

Leetcode1-两数之和详解

Leetcode2-两数相加代码详解

Leetcode20-有效的括号详解

Leetcode21-合并两个有序链表详解

Leetcode22-有效括号生成详解

Leetcode24-两两交换链表中的节点详解

Leetcode94-二叉树的中序遍历详解

Leetcode102-二叉树的层序遍历详解

题目

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

解析

广度优先算法

从上到下遍历每一层，将每一层的节点数子放入一个子集中，将每一层的子集按自底向上防毒结果集中。

初始化变量size、result和queue，其中size表示每一层节点的个数，result用来存放每一层的子集，queue为队列。

对于示例，首先从根节点3开始，第一步将节点3加入队列中，此时size的大小为队列的长度1，第二步取出队列中的节点3放入到结果集中，并将size-1

第三步将左右孩子节点放入队列中，此时size的大小为队列长度2，第四步取出队列的第一个元素放入结果集中，并将size-1

第五步取出队列中的元素20放入结果集中，并将size-1，第六步将节点20的左右孩子节点放入队列中，此时size大小为队列长度2

第七步将队列的第一个元素放入结果集中，将size-1，第八步将队列最后一个元素放入结果集中，并将size-1

深度优先算法

本题的深度优先算法流程和Leetcode102-二叉树的层序遍历是一样的，只不过将最后的result翻转一下，将自上向下遍历变为自下向上遍历

代码

广度优先搜索

from collections import deque
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        result = []
        if root is None:
            return result

        q = deque([])
        q.append(root)
        temp = deque([])
        while len(q) > 0:
            size = len(q)
            ls = []
            while size > 0:
                cur = q.popleft()
                ls.append(cur.val)
                if cur.left is not None:
                    q.append(cur.left)
                if cur.right is not None:
                    q.append(cur.right)
                size = size -1
            temp.appendleft(ls[:])
        result = list(temp)
        return result

深度优先搜索

from collections import deque
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        result = []
        if root is None:
            return result

        self.dfs(root, result, 0)
        result.reverse()  # 将结果翻转
        return result

    def dfs(self, node, result, level):
        if node is None:
            return

        if level > len(result)-1:
            result.append([])

        result[level] .append(node.val)

        if node.left is not None:
            self.dfs(node.left, result, level+1)
        if node.right is not None:
            self.dfs(node.right, result, level+1)

原网站

版权声明
本文为[白羊by]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_45848575/article/details/125959575