いいものをつくろう

CTOの日記

アルゴリズム

leetcode tree 祭り

投稿日:

 

[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なりでグローバル変数を持たすのが楽。

113 sum path ii

上の実装はかなりメモリの使用量が悪いので、

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%で改善されます。

https://leetcode.com/problems/path-sum-ii/discuss/465195/Python-recursive-Memory-effective-96-and-7-comparison

以上です。

 

 

-アルゴリズム
-,

Copyright© CTOの日記 , 2020 All Rights Reserved.