[easy] just traverse and print
[medium] collecting values in array
https://leetcode.com/problems/trim-a-binary-search-tree
post-orderでの比較とtrimをうまくできた。再起の関数として
一番、layerの低いnodeを返す関数と定義したのが、素晴らしいポイント！mini < X < maxiの条件により残す枝はどちらか
一方に必ず定まる
https://leetcode.com/problems/path-sum
この問題は、発想は簡単に思いついた。
問題の条件でリーフまで達した時に、という条件をちゃんと実装できるかどうか？
is_leaf = (node.left == None and node.right == None)
あとはエッジケースのもし、sum=0のときも注意ですね。
tree問題で配列を集めないと行けない場合は、dfsの場合はselfなりでグローバル変数を持たすのが楽。
上の実装はかなりメモリの使用量が悪いので、
recursiveの場合は、一回ごとにunwindするのが、定石だ！
https://leetcode.com/problems/path-sum-ii/discuss/464828/Java-solution-100-Recursive
おわかりいただけただろうか。この部分です。
//after the recursion has unwinded, remove the currNode's value before returning currList.remove(currList.size() - 1); currSum = currSum - root.val;
非常に重要だと思うのでpythonでも書いてみます。
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res = []
def rec(node: TreeNode, goal, acc, path):
if node is None: return
path.append(node.val)
_acc = (acc if acc else 0) + node.val
if _acc == goal and node.left is None and node.right is None:
copied = path[:]
res.append(copied)
rec(node.left, goal, _acc, path)
rec(node.right, goal, _acc, path)
# revert
path.pop()
rec(root, sum, None, [])
return res
とするとメモリが96%で改善されます。
以上です。