Day 15 二叉樹: 層序遍歷, 226. 翻轉(zhuǎn), 101. 對稱, 102. 層序, 199. 右視圖, 116|117. 填充右側(cè)節(jié)點 I II

層序遍歷：本質(zhì)是BFS.

102. 二叉樹的層序遍歷

思路
- example
- 迭代法份企。FIFO，用隊列deque存儲遍歷節(jié)點。
復雜度. 時間：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

遞歸寫法睹栖，本質(zhì)是DFS, 前序遍歷惠赫。
- 用depth標記層數(shù)（深度）

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
- 層序遍歷鞍匾，最后一步反轉(zhuǎn)即可: 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
- 層序遍歷愁拭，取每一層最后一個數(shù)字即可讲逛。
復雜度. 時間：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. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針

思路
- example
- 完美二叉樹: 所有葉子節(jié)點都在同一層许赃，每個父節(jié)點都有兩個子節(jié)點.
- 層序遍歷，當前節(jié)點.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

進階: 空間, 鏈表解法
- 注意每個節(jié)點默認的next為None

利用next遍歷每一層節(jié)點
利用left,right鏈接下一層的節(jié)點
first: 每層的第一個節(jié)點

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        first = root
        while first:
            cur = first
            while cur: # 遍歷每一層節(jié)點
                if cur.left: # 左節(jié)點next=cur.right 
                    cur.left.next = cur.right
                if cur.right and cur.next: # 右節(jié)點next=cur.next.left
                    cur.right.next = cur.next.left 
                cur = cur.next # 同層節(jié)點
            first = first.left # 下一層起始節(jié)點
        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. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針 II

思路
- example
- 普通二叉樹.
- 迭代寫法與上一題沒有區(qū)別。
復雜度. 時間：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. 翻轉(zhuǎn)二叉樹

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

前序遍歷沟于，迭代寫法咳胃。
- 交換左右子節(jié)點。

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

層序遍歷(迭代)也可以社裆。
- 交換左右子節(jié)點拙绊。

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
- 本質(zhì)：比較兩棵子樹。
  - 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用迭代實現(xiàn): 一次加入兩個對應(yīng)的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 層序遍歷實現(xiàn)也可以
- 每一層對稱

TBA

最后編輯于：2023.10.02 02:02:48

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末金句，一起剝皮案震驚了整個濱河市檩赢，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌违寞，老刑警劉巖贞瞒，帶你破解...
沈念sama閱讀 206,482評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異趁曼，居然都是意外死亡军浆，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,377評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門挡闰，熙熙樓的掌柜王于貴愁眉苦臉地迎上來乒融，“玉大人，你說我怎么就攤上這事摄悯≡藜荆” “怎么了？”我有些...
開封第一講書人閱讀 152,762評論 0贊 342
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵奢驯，是天一觀的道長申钩。經(jīng)常有香客問我，道長瘪阁，這世上最難降的妖魔是什么撒遣？我笑而不...
開封第一講書人閱讀 55,273評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮管跺，結(jié)果婚禮上愉舔，老公的妹妹穿的比我還像新娘。我一直安慰自己伙菜，他們只是感情好，可當我...
茶點故事閱讀 64,289評論 5贊 373
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布命迈。她就那樣靜靜地躺著贩绕，像睡著了一般。火紅的嫁衣襯著肌膚如雪壶愤。梳的紋絲不亂的頭發(fā)上淑倾，一...
開封第一講書人閱讀 49,046評論 1贊 285
城市分裂傳說
那天，我揣著相機與錄音征椒，去河邊找鬼娇哆。笑死，一個胖子當著我的面吹牛，可吹牛的內(nèi)容都是我干的碍讨。我是一名探鬼主播治力，決...
沈念sama閱讀 38,351評論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼勃黍！你這毒婦竟也來了宵统？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 36,988評論 0贊 259
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤覆获，失蹤者是張志新（化名）和其女友劉穎马澈，沒想到半個月后，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體弄息，經(jīng)...
沈念sama閱讀 43,476評論 1贊 300
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡痊班，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 35,948評論 2贊 324
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了摹量。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片涤伐。...
茶點故事閱讀 38,064評論 1贊 333
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖荆永，靈堂內(nèi)的尸體忽然破棺而出废亭，到底是詐尸還是另有隱情，我是刑警寧澤具钥，帶...
沈念sama閱讀 33,712評論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布豆村，位于F島的核電站，受9級特大地震影響骂删，放射性物質(zhì)發(fā)生泄漏掌动。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 39,261評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一宁玫、第九天我趴在偏房一處隱蔽的房頂上張望粗恢。院中可真熱鬧，春花似錦欧瘪、人聲如沸眷射。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,264評論 0贊 19
一樁弒父案佛掖，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽妖碉。三九已至，卻和暖如春芥被，著一層夾襖步出監(jiān)牢的瞬間欧宜，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,486評論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工拴魄，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留冗茸，地道東北人矛紫。一個月前我還...
沈念sama閱讀 45,511評論 2贊 354
代替公主和親
正文我出身青樓祭犯，卻偏偏與公主長得像洋丐，于是被迫代替她去往敵國和親吊圾。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
茶點故事閱讀 42,802評論 2贊 345

Day 15 二叉樹: 層序遍歷, 226. 翻轉(zhuǎn), 101. 對稱, 102. 層序, 199. 右視圖, 116|117. 填充右側(cè)節(jié)點 I II

推薦閱讀更多精彩內(nèi)容