灵神基础算法精讲-13-学习笔记

102. 二叉树的层序遍历（广度优先搜索）

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

思路

层序遍历是一行一行地遍历。

做法1

初始化一个 cur 数组，把根节点放进去，然后开始循环，再创建一个 nxt(next) 数组，遍历 cur 数组中的每个节点，把他的左右儿子都放到 nxt 数组中，如果儿子是空的就不放，把 cur 遍历完之后就得到下一层的节点了。

在遍历的同时还需要把节点值放到一个 vals 数组中，最后把这个数组加到答案里。

遍历结束后，把 cur 替换成 nxt 就可以开启下一轮循环了。

当遍历到最底层的节点时，其 nxt 数组为空，进入下一轮循环时，cur 替换成 nxt 也为空，因此，可以根据 cur 是否为空来判断是否退出循环。

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        
        cur = [root]
        ans = []

        while cur:
            nxt = []
            vals = []
            for node in cur:
                vals.append(node.val)
                if node.left:
                    nxt.append(node.left)
                if node.right:
                    nxt.append(node.right)
            ans.append(vals)
            cur = nxt
        return ans

时间复杂度：由于每个节点只会遍历一次，所以时间复杂度为 O(n)。

空间复杂度：由于在满二叉树的情况下，也就是每一层都填满时，最后一层大约有 n/2 个节点，所以空间复杂度是 O(n)。

做法2

做法1用了两个数组 cur 和 nxt，思考只用一个数组或某个数据结构，将 cur 和 nxt 这两个数组拼起来。把当前层的节点去掉，并把下一层的节点加到末尾，这种【左出右进】【先进先出】的数据结构，叫做队列（Queue）。

怎么知道每一层要循环多少次？这就是队列的长度，在循环开始的时候，获取队列的长度，然后循环这么多次就可以得到下一层的节点了。

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        ans, q = [], [root]
        
        while q:
            vals = []
            for _ in range(len(q)):
                node = q.pop(0)
                vals.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(vals)
        return ans

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

思路

只需要在二叉树层序遍历的基础上，把偶数层的数组翻转一下就可以了。

# 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 zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        
        ans, q = [], [root]
        even = False

        while q:
            vals = []
            for _ in range(len(q)):
                node = q.pop(0)
                vals.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(vals[::-1] if even else vals) 
            even = not even
        return ans

513. 找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

思路

1. 思路1: 层序遍历时，返回最后一层的第一个节点
2. 思路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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = [root]
        while q:
            node = q.pop(0)
            if node.right:
                q.append(node.right)
            if node.left:
                q.append(node.left)
        return node.val