It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
As a countermeasure, it seems that a site called Let Code will take measures.
A site that trains algorithmic power that can withstand coding tests that are often done in the home.
I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day 39 "494. Target Sum" starting from zero
Basically, I would like to solve the easy acceptance in descending order.
Twitter I'm doing it.
This is the 40th time. I don't know when to quit.
114. Flatten Binary Tree to Linked List
The difficulty level is Medium. Excerpt from Top 100 Liked Questions.
Given a binary tree, design an algorithm that transforms it into a flat list.
This alone is difficult to understand, so let's look at an example.
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
After all it is easy to understand if you look at the example.
# 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: TreeNode) -> None:
prelevel = None
"""
Do not return anything, modify root in-place instead.
"""
def dfs(node):
if node:
dfs(node.right)
dfs(node.left)
nonlocal prelevel
node.right = prelevel
node.left = None
prelevel = node
dfs(root)
# Runtime: 36 ms, faster than 74.14% of Python3 online submissions for Flatten Binary Tree to Linked List.
# Memory Usage: 14.6 MB, less than 8.70% of Python3 online submissions for Flatten Binary Tree to Linked List.
Solved with dfs.
Hold the element to be assigned at prelevel, assign the element to node.right, assign None to node.left, and put the next element in prelevel.
I got a good answer. This time around here. Thank you for your hard work.
Recommended Posts