F / \ B G / \ \ A D I / \ / C E H Pre-order Traversal root left subtree right subtree F B A D C E G I H https://leetcode.com/problems/binary-tree-preorder-traversal/ Iterative approach class Solution(object): def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: """ :type root: TreeNode :rtype: List[int] """ res, stack = [], [(root, False)] while stack: node, visited = stack.pop() if node: if visited: res.append(node.val) else: stack....
https://leetcode.com/problems/path-sum/solution/ ノードがリーフでない場合は、子に対してhasPathSumメソッドを再帰的に呼び出し、合計を現在のノードの値だけ減らす。 ノードがリーフの場合、現在の合計がゼロであるかどうか、つまり最初の合計が検出されたかどうかを確認します。 Base case は、root が none ということはリーフの下の node を確認してるので、sum が 0 になっていないので False を返す。 class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False targetSum -= root.val if not root.left and not root.right: # if reach a leaf return targetSum == 0 return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)
DFS Base Case root が Null は None を返す。 Tree を反転して値が同じなら True を返すので、 children node の値を swap して同じか確かめる。 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 invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if not root: return None tmp = root....
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...