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 25 "70. Climbing Stairs" starting from zero
Basically, I would like to solve the easy acceptance in descending order.
Twitter I'm doing it.
543. Diameter of Binary Tree The difficulty level is easy. Excerpt from Top 100 Liked Questions.
Given a binary tree, return the diameter of that tree. The diameter here refers to the passage that goes back and forth the longest distance between each node.
Example:
Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
In this case, the longest is from 4 to 3 and from 5 to 3, and the number of branches in between is 3, so 3 is returned.
It was a depth-first search.
# 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: 44 ms, faster than 72.73% of Python3 online submissions for Diameter of Binary Tree.
# Memory Usage: 15.9 MB, less than 51.72% of Python3 online submissions for Diameter of Binary Tree.
The basic flow is the same as that of a general depth-first search. However, since it is necessary to check the length this time, I prepared a variable ʻans` for that and added a calculation.
Even with the problems of trees in the past, I only write depth-first search, so I think I should study breadth-first search soon. It's too late today, so that's it, thank you.
If there is another good answer, I will add it.
Recommended Posts