[Leetcode] 1161. Maximum Level Sum of a Binary Tree (Medium)

概述

題目

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/
給定一個樹，求哪一層數值和最大

心得

Traverse 一次後求該層數值，取最大者

Traverse

思路

暴力將每層數值取出來，然後求其該層和，回傳最大層

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxLevelSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0

		# 求各分層數值模板
        def trv(root):
            if root == None:
                return
            self.lvl += 1
            if self.lvl > len(self.arr):
                self.arr.append([root.val])
            else:
                self.arr[self.lvl-1].append(root.val)
            trv(root.left)
            trv(root.right)
            self.lvl -= 1
        self.lvl = 0
        self.arr = []
        trv(root)
        
        # 若有最大和相等，求其最小層
        arr = [sum(c) for c in self.arr]

        return arr.index(max(arr))+1

邊 Traverse 邊計算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxLevelSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0

        def trv(root):
            if root == None:
                return
            self.lvl += 1
            if self.lvl > len(self.arr):
                self.arr.append(root.val)
            else:
                self.arr[self.lvl-1] += root.val
            trv(root.left)
            trv(root.right)
            self.lvl -= 1
        self.lvl = 0
        self.arr = []
        trv(root)

        return self.arr.index(max(self.arr))+1

Complexity

Time Complexity: O(n)
Trverse 1 輪

Space Complexity: O(n)
存一 n 個數之 array

BFS

思路

每層遇到直接計算，最終全部算完找最大層

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxLevelSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0

        q = deque()
        q.append(root)
        arr = []

        while q:
            l = len(q)
            cnt = 0
            flg = 0
            for i in range(l):
                cur = q.popleft()
                if cur != None:
                    flg = 1
                    cnt += cur.val
                    q.append(cur.left)
                    q.append(cur.right)
            if flg == 1:
                arr.append(cnt)

        return arr.index(max(arr))+1

Complexity

Time Complexity: O(n)
Trverse 1 輪

Space Complexity: O(n)
存一 n 個數之 deque

Recursive

思路

重覆求其左右

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxLevelSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        dic = Counter()
        def trv(root, depth):
            if root != None:
                dic[depth] += root.val
                trv(root.left,  depth+1)
                trv(root.right, depth+1)
        
        trv(root, 1)
        return max(dic, key=dic.get)

Complexity

Time Complexity: O(n)
Trverse 1 輪

Space Complexity: O(n)
存一 n 個數之 dic