Leetcode_119

---

layout: single title: “23.04.19 Today’s Leetcode” tags: leetcode categories: leetcode —

## 1372. Longest ZigZag Path in a Binary Tree (medium)

DFS Approach

  # 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 longestZigZag(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(cur, prev_dir, count):
            nonlocal res
            res = max(res, count)
            if not cur:
                return
            if prev_dir:
                dfs(cur.right, False, count + 1)
                dfs(cur.left, True, 1)
            else:
                dfs(cur.left, True, count + 1)
                dfs(cur.right, False, 1)
        
        dfs(root, False, 0)
        dfs(root, True, 0)
        return res - 1

721. Accounts Merge (medium)

class Solution:
    def accountsMerge(self, A):
        G, seen, ans = defaultdict(list), set(), []

        for acc in A:
            for i in range(2, len(acc)):
                G[acc[i]].append(acc[i-1])
                G[acc[i-1]].append(acc[i])

        def dfs(email):
            seen.add(email)
            emailList = [email]
            for E in G[email]:
                if E not in seen:
                    emailList.extend(dfs(E))
            return emailList
        for acc in A:
            if acc[1] not in seen:
                ans.append([acc[0]] + sorted(dfs(acc[1])))
        return ans