solve

problem

This was the first problem I did that I needed a bit of help, but once I saw that max_path state should be kept as a global variable, it made the coding much easier. I also needed the hint for max(left, 0); 0 implying that we don't take the left.

Will need to review this problem.

from typing import Optional
# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.max_path = -1001
        self.dfs(root)
        return self.max_path
    
    # returns maxEdge
    def dfs(self, node) -> int:

        if not node:
            return 0

        left = max(self.dfs(node.left), 0)
        right = max(self.dfs(node.right), 0)
        self.max_path = max(self.max_path, left + right + node.val)
        
        return max(left + node.val, right + node.val)

problem

Same as the last problem. We only want to add when there's no left or right node. State is kept by function.

from typing import Optional
# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
        return self.dfs(root, 0)
    
    def dfs(self, node, currSum) -> int:

        if node == None:
            return 0
        
        if node.left == None and node.right == None:
            return int(str(currSum) + str(node.val))
        
        else:
            currSum = str(currSum) + str(node.val)
            return self.dfs(node.left, currSum) + self.dfs(node.right, currSum)

Problem

DFS, simple question: only check when we are at a leaf node (somehow my solution was top 99% in terms of both time and space complexity)

from typing import Optional
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        return self.dfs(root, currSum=0, targetSum=targetSum)

    def dfs(self, root, currSum, targetSum) -> bool:

        if not root:
            return False
        
        if not root.left and not root.right:
            if root.val + currSum == targetSum:
                return True

        else:
            currSum = root.val + currSum
            return self.dfs(root.left, currSum, targetSum) or self.dfs(root.right, currSum, targetSum)

problem

I understand the solution but it's a bit difficult for me to come up on the spot. Need review.

from typing import Optional
# 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 flatten(self, root: Optional[TreeNode]) -> None:
        self.dfs(root)
    
    def dfs(self, root):
        if not root:
            return None
        
        left = self.dfs(root.left)
        right = self.dfs(root.right)

        if left:
            left.right = root.right
            root.right = root.left
            root.left = None
        
        if right:
            return right
        elif left:
            return left
        return root

Still taking it easy. It's a binary tree week and just taking it easy because I'm tired.

problem

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root):
        self.process_row([root])
        return root
    
    def process_row(self, row_list):
        next_row = []
        for n in row_list:
            if n == None:
                continue
            if n.left:
                next_row.append(n.left)
            if n.right:
                next_row.append(n.right)
        
        if not next_row:
            return

        for i, n in enumerate(next_row[:len(next_row)-1]):
            n.next = next_row[i+1]

        self.process_row(next_row)

It's MLK day, here's some more binary tree questions

preorder and inorder: problem

from typing import Optional
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:

        if not preorder:
            return None

        val = preorder[0]

        split_index = -1
        for i, v in enumerate(inorder):
            if v == val:
                split_index = i

        left_preorder = preorder[1:1+split_index]
        right_preorder = preorder[1+split_index:]
        left_inorder = inorder[0:split_index]
        right_inorder = inorder[split_index+1:]

        return TreeNode(
            val = val,
            left = self.buildTree(left_preorder, left_inorder),
            right = self.buildTree(right_preorder, right_inorder)
        )

inorder and postorder: problem

from typing import Optional
# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder:
            return None
        val = postorder[-1]
        split_index = -1
        for i, v in enumerate(inorder):
            if v == val:
                split_index = i
        left_inorder = inorder[0:split_index]
        right_inorder = inorder[split_index+1:]
        left_postorder = postorder[0:split_index]
        right_postorder = postorder[split_index:len(postorder)-1]

        return TreeNode(
            val=val,
            left=self.buildTree(left_inorder, left_postorder),
            right=self.buildTree(right_inorder, right_postorder)
        )

It's still the weekend so taking it easy. Some binary tree questions.

problem

from typing import Optional
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.is_mirror(root.left, root.right)
    
    def is_mirror(self, p, q):
        if p is None and q is None:
            return True
        elif p is not None and q is None:
            return False
        elif p is None and q is not None:
            return False
        # elif p is not None and q is not None:
        if p.val != q.val:
            return False
        
        return self.is_mirror(p.right, q.left) and self.is_mirror(p.left, q.right)

problem

from typing import Optional
# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return None
        placeholder = root.left
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(placeholder)
        return root

The next few problems these days are all going to be binary tree problems. Starting off easy because it's the weekend

problems

from typing import Optional
# De