DFS recursive Base Case は p,q が Null の場合同じ Tree なので return する。 もし p,q のどちらかの値が違う場合、その Tree は同じではないので、 False を return する。 また、どちらかの値が Null の場合同じ Tree ではないので、この場合も False を　return する。 Time complexity: O(n) Mem complexity: O(n) # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if not p and not q: return True if not p or not q or p....

回答のアプローチは Recursive DFS BFS Iterative DFS Base case root が empty children が Null Recursive DFS Time complexity: O(n) Mem complexity: O(n) class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) BFS BFS を使う場合は Queue を使う。 3 ／　＼ 9 20 ／＼ 15 7 | 3 | 9 | 20 | 15 | 7 | 1 2 2 3 3 ← Level...

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/ この問題の回答方法としては Recursive と Iterative なアプローチがある。 Recursive Approach アルゴリズム ルートの Node から始める。 p と q が右の subtree にある場合、1から右のsubtreeを探すようにする。 p と q が左の subtree にある場合、1から左のsubtreeを探すようにする。 もし 2 と 3 のステップが not true の場合、p と q の共通の Node を見つけたこととなる。 Time complexity: O(n) Mem complexity: O(n) # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ parent_val = root....

https://leetcode.com/problems/climbing-stairs/ n = 5 0 ／　＼ 1 2 ／＼ ／＼ 2 3 3 4 ／＼ ／＼ ／＼ ／＼ 3 4 4 5 4 5 5 6 ／＼ ／＼ ／＼　／＼ 4 5 5 6 5 6　5 6 ／＼ 5 6 n が 5 steps の場合、 8通りの選択が出来る。 DFS でも出来るかが 2^n となる。 そのため Dynamic Programming を使う。 同じ計算をする値は memoize する | 8 | 5 | 3 | 2 | 1 | 1 | n に辿り着くまでの数 0 1 2 3 4 5(step) one two...

https://leetcode.com/problems/meeting-rooms/ 先ず始めに intervals のスタート時間でソートする。 intervals の時間がソートされたため、 ループで最初の会議の終わりの時間と次の会議の始まりの時間を比較し、 最初の会議の終わりの時間 が 次の会議の始まりの時間より大きい場合、 会議の時間が重なっているので、False を返す。 次の会議の開始時間 が 前の会議の終わり時間より小さい場合ループを続ける。 ループする際、次のリストと比較するため for の range で -1 をする。 ソートをするので Time complexity は O(n log n) となる。 Time complexity: O(n log n) Mem complexity: O(1) class Solution(object): def canAttendMeetings(self, intervals): """ :type intervals: List[List[int]] :rtype: bool """ intervals.sort() for i in range(len(intervals) -1): if intervals[i][1] > intervals[i + 1][0]: return False return True