[LeetCode] 428. Serialize and Deserialize N-ary Tree

 Problem: https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/

Use preorder traversal to dump the given tree. To make the deserialize process simpler, we dump the size of children list after the node value to indicate how many children node is needed under current node.

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Codec:
    def serialize(self, root: 'Node') -> str:
        """Encodes a tree to a single string.
        
        :type root: Node
        :rtype: str
        """
        
        def preorder(node):
            yield str(node.val)
            yield str(len(node.children))
            
            for nxt in node.children:
                yield from preorder(nxt)
            
        return ','.join(preorder(root)) if root else ''
	
    def deserialize(self, data: str) -> 'Node':
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: Node
        """
        
        data = data.split(',') if data else []
        

        def helper(index):
            if index >= len(data):
                return None, index
            
            node = Node(val=int(data[index]), children=[])
            index += 1
            size = int(data[index])
            index += 1
            
            for _ in range(size):
                child, index = helper(index)
                node.children.append(child)
                
            return node, index
                
        return helper(0)[0]

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

[LeetCode] 565. Array Nesting

 Problem: https://leetcode.com/problems/array-nesting/

According to the given rule,  a valid set is built upon with the values of nums[k], nums[nums[k]], ...

We can use Union-Find to build set. Then return size of the largest set as result.

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
       
    def union(self, a, b):
        ap = self.find(a)
        bp = self.find(b)
        
        if ap != bp:
            self.parent[bp] = ap
     
    def find(self, a):
        if self.parent[a] != a:
            self.parent[a] = self.find(self.parent[a])
        return self.parent[a]

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        uf = UnionFind(len(nums))
        
        # build the sets
        for a, b in enumerate(nums):
            if a != b:
                uf.union(a, b)
        
        # get size of the largest set
        count = defaultdict(int)
        
        for i in range(len(nums)):
            count[uf.find(i)] += 1
        
        return max(count.values())

[LeetCode] 1161. Maximum Level Sum of a Binary Tree

 Problem : https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

This is an easy problem which can be solved by either DFS or BFS.

But it needs to be aware that because node may have negative value, we cannot determine the final sum of a level until traversal is completed. 

Time Complexity = O (N + N)

# 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 maxLevelSum(self, root: Optional[TreeNode]) -> int:
        levels = []
        stack = [(root, 0)]
        
        while stack:
            node, index = stack.pop()
            
            if index == len(levels):
                levels.append(node.val)
            else:
                levels[index] += node.val
 
            if node.right:
                stack.append((node.right, index + 1))
            if node.left:
                stack.append((node.left, index + 1))
        
        mxSoFar = levels[0]
        miLevel = 0
        
        for level, sums in enumerate(levels):
            if sums > mxSoFar:
                mxSoFar = sums
                miLevel = level
        
        return miLevel + 1

[LeetCode] 742. Closest Leaf in a Binary Tree

 Problem : https://leetcode.com/problems/closest-leaf-in-a-binary-tree/

Because the goal is to find the nearest leaf node,  we use postorder to keep the shortest path to a leaf in left sub-tree or right sub-tree. 

If current node's value == k,  we use the shorter path from left or right sub-tree as the potential result. 

If k does not exist in either left sub-tree or right sub-tree, we only keep the shorter path

If k exists in left sub-tree, we consider path-to-value-k-in-left-sub-tree + shortest-path-to-leaf-in-right-sub-tree as potential result.

Similar procedure when k exists in right sub-tree.

This problem cannot solve by preorder traversal, because it cannot locate the lowest common ancestor with preorder traversal. 

Lesson learned:

- Postorder is useful we need to build path from leaf. 

- On each node, we can build a path by connecting path from left tree and path from right tree.

- We can return as much info as we need in postorder traversal.

# 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 findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:
        self.result = None
        
        def postorder(node):
            if not node.left and not node.right:
                if node.val == k:
                    self.result = (0, k)
                    
                return (1, node.val == k, node.val)
            
            leftDepth, leftHasK, leftLeaf = postorder(node.left) if node.left else (1000, False, -1)
            rightDepth, rightHasK, rightLeaf = postorder(node.right) if node.right else (1000, False, -1)
            
            
            if node.val == k:
                if leftDepth < rightDepth:
                    self.result = (leftDepth, leftLeaf)
                    return (1, True, -1)
                else:
                    self.result = (rightDepth, rightLeaf)
                    return (1, True, -1)
            elif leftHasK:
                if leftDepth + rightDepth < self.result[0]:
                    self.result = ((leftDepth + rightDepth), rightLeaf)

                return (leftDepth+1, True, -1)
            elif rightHasK:
                if rightDepth + leftDepth < self.result[0]:
                    self.result = ((rightDepth + leftDepth), leftLeaf)

                return (rightDepth+1, True, -1)
            else:
                if leftDepth < rightDepth:
                    return (leftDepth+1, False, leftLeaf)

                return (rightDepth+1, False, rightLeaf)
            
        
        postorder(root)
        
        return self.result[1]

[LeetCode] 670. Maximum Swap

 Problem : https://leetcode.com/problems/maximum-swap/

To get maximum value, we need to have the larger digits on the higher end.

class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = []
        
        # get digits
        while num:
            digits.append(num % 10)
            num = num // 10
        
        digits = digits[::-1]
        
        # find the max digits on right of each position
        N = len(digits)
        mxFromRight = [0] * N
        
        mxFromRight[N-1] = N-1
        mxForNow = N-1
        
        for i in reversed(range(N)):
            if digits[mxForNow] < digits[i]:
                mxForNow = i
            
            mxFromRight[i] = mxForNow
        
        for i in range(N):
            # iterate from left and swap the first digit not equal to the maximum digit from right side.
            if digits[i] == digits[mxFromRight[i]] :
                continue
            
            digits[i], digits[mxFromRight[i]] =  digits[mxFromRight[i]],  digits[i]
            break
        
        # assemble the final result
        result = 0
        for i in range(N):
            result = result * 10
            result += digits[i]
        
        return result

[LeetCode] 921. Minimum Add to Make Parentheses Valid

 Problem : https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/

Use stack to match left parenthesis with right parenthesis as much as possible.

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        stack = []
        
        for w in s:
            if w == '(':
                stack.append(w)
            elif stack and stack[-1] == '(':
                stack.pop()
            else:
                stack.append(w)
        
        return len(stack)

[LeetCode] 652. Find Duplicate Subtrees

 Problem : https://leetcode.com/problems/find-duplicate-subtrees/

A tree can be represented by its path. 2 trees are identical if their dumped paths are the same.

Use postorder traversal to find sub-trees with same dumped path.

# 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 findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        
        seen = defaultdict(list)
        result = []
        
        def postorder(node):
            if not node: return "#"
            
            key = '(' + str(node.val) + ')'+ postorder(node.left) + postorder(node.right)
            seen[key].append(node)
            
            if len(seen[key]) == 2:
                result.append(node)
            
            return key
        
        postorder(root)
        
        return result

[LeetCode] 1448. Count Good Nodes in Binary Tree

 Problem : https://leetcode.com/problems/count-good-nodes-in-binary-tree/

Use DFS to find number of nodes where value not less than the current local maximum value.

# 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 goodNodes(self, root: TreeNode) -> int:
        
        result = 0
        stack = [(root, -10**4)]
        
        while stack:
            node, mx = stack.pop()
            
            if mx <= node.val:
                result += 1
                mx = node.val
            
            if node.right:
                stack.append((node.right, mx))
            
            if node.left:
                stack.append((node.left, mx))
        
        return result

[LeetCode] 1762. Buildings With an Ocean View

 Problem : https://leetcode.com/problems/buildings-with-an-ocean-view/

Maintain a decreasing monotonic stack.

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        stack = []
        
        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] <= h:
                stack.pop()
            
            stack.append(i)
        
        return stack

[LeetCode] 1019. Next Greater Node in Linked List

 Problem : https://leetcode.com/problems/next-greater-node-in-linked-list/

Use postorder traversal and maintain a decreasing monotonic stack.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        result = []
        
        def postorder(node):
            if node.next:
                stack = postorder(node.next)
                while stack and stack[-1] <= node.val:
                    stack.pop()
                
                result.append(stack[-1] if stack else 0)                
                stack.append(node.val)
                
                return stack
            else:
                result.append(0)
                return [node.val]
        
        postorder(head)
        return result[::-1]

Or maintain a increasing monotonic stack which also saves the position of each smaller value.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
        result = []
        stack = []
        
        while head:
            while stack and stack[-1][1] < head.val:
                result[stack[-1][0]] = head.val
                stack.pop()
            
            stack.append([len(result), head.val])
            result.append(0)
            
            head = head.next
        
        return result