はじめに
LeetCodeの問題を解答します。
なるべく、問題の和訳と詳細なコメントを書いています。
余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。
様々なカテゴリの問題をランダムにあたる方法も良いですが、
二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。
テーマごとに問題を分類しました。
LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。
また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。
はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。
ポイント
-
- DFS
詳細
問題
原文
Given a binary tree
root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.Return the number of good nodes in the binary tree.
Example 1:
Example 2:
Example 3:
Constraints:
- The number of nodes in the binary tree is in the range
[1, 10^5].- Each node’s value is between
[-10^4, 10^4].
内容(和訳)
与えられた二分木の根を root とすると、木の中のノード X が「良い (good)」と呼ばれる条件は、根から X に至るパス上に、X より大きな値を持つノードが存在しない場合です。
二分木の中の「良い」ノードの数を返してください。
※chatGPTによる翻訳
解答
解答1：Python, 再帰
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# 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 goodNodes(self, root: TreeNode) -> int: self.number = 0 max_value = root.val self.DFS(root, max_value) return self.number def DFS(self, node, max_value): if node.val >= max_value: self.number += 1 max_value = max(max_value, node.val) if node.right: self.DFS(node.right, max_value) if node.left: self.DFS(node.left, max_value) |
ノードがあるたびにDFSメソッドを呼び出す。
DFSメソッドでは、パスの最大値を保持しており、呼び出される都度以下を行う。
・現在のノードの値がパスの最大値よりも大きければnumberをインクリメント
※パスとは、そのノードまでの経路
・パスの最大値と現在のノードの値を比較して最大値を更新
・左右の子ノードがあれば再帰呼び出し
numberはDFSメソッドに都度渡すのではなく、Solutionクラス全体をスコープに持つ変数としている。
DFSというよりはメモ化再帰のような気がする。
終わりに
補足・参考・感想
問題を分類しました。テーマごとに集中して問題を解くことができます。
LeeetCodeの問題をアルゴリズムとデータ構造による分類
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。
他の問題もどうぞ
次：700. Search in a Binary Search Tree
コメント