Day 15 二叉树: 层序遍历, 226. 翻转, 101. 对称, 102. 层序, 199. 右视图, 116|117. 填充右侧节点 I II

层序遍历：本质是BFS.

102. 二叉树的层序遍历

思路
- example
- 迭代法。FIFO，用队列deque存储遍历节点。
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        que = collections.deque()
        if root: # !!!
            que.append(root)
        while que:
            size = len(que)
            temp = []
            for _ in range(size):
                node = que.popleft()
                temp.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(temp)
        return res

递归写法，本质是DFS, 前序遍历。
- 用depth标记层数（深度）

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        def dfs(root, depth):
            if not root: 
                return 
            if len(res) == depth: res.append([]) # start the current depth
            res[depth].append(root.val) # fulfil the current depth
            if  root.left: 
                dfs(root.left, depth + 1) # process child nodes for the next depth
            if  root.right: 
                dfs(root.right, depth + 1)
        dfs(root, 0)
        return res

107. 二叉树的层序遍历 II

思路
- example
- 层序遍历，最后一步反转即可: res.reverse()
- 或者用stack，按照右左顺序入栈。
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        que = collections.deque()
        if root:
            que.append(root)
        while que:
            size = len(que)
            temp = []
            for _ in range(size):
                node = que.popleft()
                temp.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right) 
            res.append(temp)
        res.reverse()
        return res

199. 二叉树的右视图

思路
- example
- 层序遍历，取每一层最后一个数字即可。
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        res = []
        que = collections.deque([root])
        while que:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if i == size - 1:
                    res.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return res

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        que = collections.deque()
        if root:
            que.append(root)
        while que:
            size = len(que)
            temp = []
            for _ in range(size):
                node = que.popleft()
                temp.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(temp[-1])
        return res

637. 二叉树的层平均值

思路
- example
- 层序遍历，每层计算平均值。
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        res = []
        if root:
            que = collections.deque([root])
        while que:
            size = len(que)
            sum_ = 0
            for _ in range(size):
                node = que.popleft()
                sum_ += node.val 
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(sum_ / size)
        return res

429. N 叉树的层序遍历

思路
- example
- 层序遍历，多个children
复杂度. 时间：O(n), 空间: O(n)

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        res = []
        que = collections.deque()
        if root:
            que.append(root)
        while que:
            size = len(que)
            temp = []
            for _ in range(size):
                node = que.popleft()
                temp.append(node.val)
                for child in node.children:
                    if child:
                        que.append(child)
            res.append(temp)
        return res

515. 在每个树行中找最大值

思路
- example
- 层序遍历，每层求最大值。
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        que = collections.deque()
        if root:
            que.append(root)
        while que:
            size = len(que)
            max_ = -float('inf')
            for _ in range(size):
                node = que.popleft()
                max_ = max(max_, node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            res.append(max_)
        return res

116. 填充每个节点的下一个右侧节点指针

思路
- example
- 完美二叉树: 所有叶子节点都在同一层，每个父节点都有两个子节点.
- 层序遍历，当前节点.next = que[0] if i != size - 1. 避免使用pre指针。
  - 维护pre指针亦可
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        que = collections.deque()
        if root:
            que.append(root)
        while que:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if i != size - 1:
                    node.next = que[0]
                else:
                    node.next = None
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return root

进阶: 空间, 链表解法
- 注意每个节点默认的next为None

利用next遍历每一层节点
利用left,right链接下一层的节点
first: 每层的第一个节点

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        first = root
        while first:
            cur = first
            while cur: # 遍历每一层节点
                if cur.left: # 左节点next=cur.right 
                    cur.left.next = cur.right
                if cur.right and cur.next: # 右节点next=cur.next.left
                    cur.right.next = cur.next.left 
                cur = cur.next # 同层节点
            first = first.left # 下一层起始节点
        return root

更一般的写法 (可推广至II)

cur: 上级指针，上层已链接好
pre:下层pre指针

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        first = root  
        while first: # first: first node in the current level 
            cur = first 
            dummyhead = Node(-1)
            pre = dummyhead 
            while cur: # traverse node in the current level
                if cur.left:
                    pre.next = cur.left 
                    pre = cur.left 
                if cur.right:
                    pre.next = cur.right 
                    pre = cur.right 
                cur = cur.next 
            first = dummyhead.next
        return root

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root == None:
            return root  
        cur = root  
        while cur:
            dummyhead = Node(-1,None,None,None)  
            pre = dummyhead  
            while cur: 
                if cur.left:
                    pre.next = cur.left  
                    pre = cur.left 
                if cur.right:
                    pre.next = cur.right  
                    pre = cur.right 
                cur = cur.next 
            cur = dummyhead.next 
        return root

117. 填充每个节点的下一个右侧节点指针 II

思路
- example
- 普通二叉树.
- 迭代写法与上一题没有区别。
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root == None:
            return None
        que = collections.deque([root])
        while que:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if i != size - 1:
                    node.next = que[0]
                else:
                    node.next = None
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return root

进阶: 空间 $O(1)$
链表解法，使用dummyhead
使用pre指针来链接下一层Node (cur和pre是相邻两层的移动指标）
参考

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root == None:
            return None
        first = root
        while first: # 遍历每一层
            cur = first 
            dummyhead = Node(0)
            pre = dummyhead
            while cur: # 链接下一层
                if cur.left: 
                    pre.next = cur.left 
                    pre = pre.next 
                if cur.right:
                    pre.next = cur.right
                    pre = pre.next 
                cur = cur.next # first-node 同层其它node
            first = dummyhead.next # 下一层first-node 
        return root

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root == None:
            return None 
        cur = root 
        while cur:
            dummyhead = Node(0, None, None, None) # next pointer must be None because it could point to cur.right
            pre = dummyhead
            while cur:
                if cur.left:
                    pre.next = cur.left 
                    pre = cur.left
                if cur.right:
                    pre.next = cur.right 
                    pre = cur.right  
                cur = cur.next 
            cur = dummyhead.next 
        return root

104. 二叉树的最大深度

思路
- example
- 层序 bfs
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        level = 0
        que = collections.deque()
        if root:
            que.append(root)
        while que:
            size = len(que)
            level += 1
            for _ in range(size):
                node = que.popleft()
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return level

dfs亦可

111. 二叉树的最小深度

思路
- example
- 层序遍历
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        res = 0
        que = collections.deque()
        if root:
            que.append(root)
        while que:
            size = len(que)
            res += 1
            for _ in range(size):
                node = que.popleft()
                if node.left == None and node.right == None:
                    return res   
                if node.left: 
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return 0

DFS亦可以。

TBA

226. 翻转二叉树

image

思路
- example
- 递归，后序遍历
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def traversal(root):
            if root == None:
                return None 
            new_left = traversal(root.left)
            new_right = traversal(root.right)
            root.left = new_right 
            root.right = new_left 
            return root 
        return traversal(root)

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return root  
        left = self.invertTree(root.left)  
        right = self.invertTree(root.right) 
        root.left = right 
        root.right = left 
        return root

前序遍历，迭代写法。
- 交换左右子节点。

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return None
        stack = [root]
        while stack:
            node = stack.pop()
            node.left, node.right = node.right, node.left 
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return root

层序遍历(迭代)也可以。
- 交换左右子节点。

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return None
        que = collections.deque([root])
        while que:
            size = len(que)
            for _ in range(size):
                node = que.popleft()
                node.left, node.right = node.right, node.left 
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return root

101. 对称二叉树

思路
- example
- 本质：比较两棵子树。
  - node1.val vs node2.val
  - node1.left vs node2.right, node1.right vs node2.left

递归：前序后序遍历混合
- 注意base case的分类。

复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def traversal(left, right):
            if left == None and right == None:
                return True 
            if left != None and right == None:
                return False 
            if left == None and right != None:
                return False 
            if left.val != right.val:
                return False 
            return traversal(left.right, right.left) and traversal(left.left, right.right)
        if root == None:
            return True 
        return traversal(root.left, root.right)

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def traverse(left_node, right_node):
            if left_node == None and right_node == None:
                return True 
            if left_node == None or right_node == None:
                return False 
            if left_node.val != right_node.val:
                return False  
            return traverse(left_node.right, right_node.left) and traverse(left_node.left, right_node.right)
        return traverse(root.left, root.right)

DFS用迭代实现: 一次加入两个对应的node进行比较。
- 队列 (TBA)
- 栈 (见下面）
  - 空指针入栈，方便比较。

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root == None:
            return True 
        stack = [root.left, root.right]
        while stack:
            right = stack.pop()
            left = stack.pop()
            if left == None and right != None: return False
            if left != None and right == None: return False
            if left == None and right == None: continue 
            if left.val != right.val: return False
            stack.append(left.left)
            stack.append(right.right)
            stack.append(left.right)
            stack.append(right.left)
        return True

BFS 层序遍历实现也可以
- 每一层对称

TBA

最后编辑于：2023.10.02 02:02:48

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 215,723评论 6赞 498
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,003评论 3赞 391
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 161,512评论 0赞 351
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,825评论 1赞 290
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,874评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,841评论 1赞 295
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,812评论 3赞 416
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,582评论 0赞 271
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,033评论 1赞 308
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,309评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,450评论 1赞 345
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,158评论 5赞 341
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,789评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,409评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,609评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,440评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,357评论 2赞 352

Day 15 二叉树: 层序遍历, 226. 翻转, 101. 对称, 102. 层序, 199. 右视图, 116|117. 填充右侧节点 I II

推荐阅读更多精彩内容