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 43 "5. Longest Palindromic Substring" starting from zero
Right now I'm solving the Top 100 Liked Questions Medium. I solved all Easy, so if you are interested, please go to the table of contents.
Twitter I'm doing it.
The difficulty level is easy. Excerpt from Top 100 Liked Questions.
I found that I had solved it but forgot to write an article, so I will write it!
The problem is given a binary tree. It looks at the diameter of the tree and designs an algorithm that returns the length of the longest path of the node between the two points.
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
In this case, 3 is returned.
# 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 diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 0
def dfs(node):
if not node:
return 0
right = dfs(node.right)
left = dfs(node.left)
self.ans = max(self.ans,left+right)
return max(left,right) + 1
dfs(root)
return self.ans
# Runtime: 40 ms, faster than 89.86% of Python3 online submissions for Diameter of Binary Tree.
# Memory Usage: 16 MB, less than 34.48% of Python3 online submissions for Diameter of Binary Tree.
Depth-first search measures the depth, and since it is a diameter, it will eventually pass through the parent, so you can solve it by adding +1.
If you can understand the structure of the tree, you can implement it relatively easily.
~~ It can't be said that it was sober ... ~~
Up to here for this time. Thank you for your hard work!
Recommended Posts