圖論應用: 找出二元樹最後一層最左邊的值 Bottom Left Tree Value_Leetcode #513

Luca Bravo on Unsplash

題目敘述

題目會給定一棵二元樹的根結點，要求我們找出這棵二元樹最後一層最左邊的值。

題目的原文敘述

測試範例

Example 1:

Input: root = [2,1,3]
Output: 1

Example 2:

Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7

約束條件

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].

節點總數量界於1~一萬之間。

• -2^31 <= Node.val <= 2^31- 1

所有節點值都落在32bits整數範圍內。

演算法 BFS 或 DFS

其實和前面介紹過的那題 二元樹的右側視角 很像。

這題題目所求為 二元樹最後一層最左邊的值。

那就依照題意，廣度優先BFS或深度優先DFS拜訪到最後一層，紀錄左手邊第一個遇到的節點值即可。

程式碼 BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution:
    def findBottomLeftValue(self, root: TreeNode) -> int:
        
        traversal_queue = [ root ]
        
        bottom_left = root
        
        while traversal_queue:
            
            next_level = []
            
            for idx, node in enumerate(traversal_queue):
                    
                if not idx:
                    # update bottom left as the first node on current level
                    bottom_left = node

                # add child node to next level traversal queue if they exist                    
                    
                if node.left:
                    next_level.append( node.left ) 

                if node.right:
                    next_level.append( node.right ) 

            traversal_queue = next_level
            
        return bottom_left.val

複雜度分析

時間複雜度:

BFS廣度優先拜訪整棵樹，每個節點至多拜訪一次。所需時間為O(n)

空間複雜度:

BFS quque所需成本為O(n)，最大成本落在最後一層。

程式碼 DFS

class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        
        def finder(node, level):
        
            if not node:
                return 
            
            if level > finder.level:
                finder.bottom_left = node.val
                finder.level = level
                
            finder(node.left, level+1)
            finder(node.right, level+1)
            return
        # -------------------------------
        
        finder.bottom_left = None
        finder.level = 0
        
        finder(node=root, level=1)
        
        return finder.bottom_left

時間複雜度:

DFS廣度優先拜訪整棵樹，每個節點至多拜訪一次。所需時間為O(n)

空間複雜度:

DFS recursion stack所需成本為O(n)，最大深度為整棵樹的最大樹高。

關鍵知識點

條條大路通羅馬，只要掌握基本原理，遇到新的題目也能根據基本的圖論演算法DFS、BFS配合題意的需求去構建出解題的演算法。

另外，還有一個衍伸題，假如題目問我們最後一層最右邊的值? 要怎麼改?

也很容易，把拜訪順序改成從右到左，取最後一層第一個遇到的節點值，就可以囉！

Reference:

[1] Find Bottom Left Tree Value - LeetCode