leetcode hard binary tree max path sum

こんにちは

今回の学びは

・再帰でもO(n)ならいい感じだよ。つまり実装してOK。

問題は。。。

まずは入出力をしっかりおさえましょう。

入力は空っぽではないTreeNodeです、ということはnullチェックもしなくていいし、そのノードが一個だけのノードだったらそのままそののノードを値を答えとして返せるわけです

出力は数字で最大値だけなので、intergerですね　得にノードをかえす必要はないようです

他にきになる問題文はありますか？

もちろん勘違いしてはいけないのはrootを通る必要はない、ということです。

それではってみよう！

実装前後でこれは毎回書きましょう。timespace anaylysis (時間とスペースの分析）は　

bfsで各ノードをスタートとしてすべての点をカバーしていくのはO(n**2)です

多分最適は操作パス一発のO(n)でいけるんじゃないかって想像します

言うは易し、実際のコードがおもいつきませんね。

マイナスにぶち当たるまで、bfsで。ぶち当たっtら、まだ検索していないノードまでdfsでとんで繰り返して終了はどうだろう。

マイナス飛ばすだけでいけるのかなー。サンプルケースでもし左ノードが9ではなく11以上だれば、マイナスをたどってもくっつけてしまったほうが、おおきいので、否。

では、これはどうだろう。再帰的にかんがえる。

まず、左サブ木の最大を求める。同様に右サブ木の最大も求める。最後にそのどちらかと、接続部分の値との合計を比較する。

このアルゴはサンプルケースではいけそうだ。

適当に他のサンプルを作ってみよう

pseudocode（擬似コード）をかいてみますか。

def maxPathSum(self, node: TreeNode) -> int:
  maxl = self.maxPathSum(node.left)
  maxr = self.maxPathSum(node.right)
  return max(maxl, maxr) + node.val

上の構想は素晴らしいものの

細部に注意しないとハマってしまう。今回のように。

実際の実装はこちら

class Solution:
    def printAll(self, root: TreeNode):
        root.p()
    def __init__(self):
        self.maxi = -sys.maxsize - 1


    def rec(self, node: TreeNode) -> int:
        if node == None: return -sys.maxsize - 1
        max_left = self.rec(node.left)
        max_right = self.rec(node.right)
        x = max(
            node.val,
            max_left, max_right,
            max_left + node.val, max_right + node.val,
            max_left + max_right + node.val)
        # print("current max is %s" % x)
        # print("max_left %s, max_right %s, node.val %s" % (max_left, max_right, node.val))
        self.maxi = max(self.maxi, x)
        if node.val < 0:
            return max(max_left + node.val, max_right + node.val)
        else:
            return x

    def maxPathSum(self, node: TreeNode) -> int:
        self.maxi = -sys.maxsize - 1
        self.rec(node)
        return self.maxi

既に、1、2回、提出エラーがあったので改良をくわえている。

リターンの場合分けと、最終的にself.maxiを返すということと、nodeがからの時は0ではなくminimum値（マイナスで最小値）を返すという点だ。

そこまでしても通らない。上のコードでは拾はleft + right + val という部分がじつはおかしいのだ。

最後はそこを修正して...

一筋なわでは行かなくなって、スパゲッティになってきました。

そういう時は、深呼吸して

図を書いたりしたり、テストケース増やしたりして行くしかないと思います

私の場合も通らなかった、以下2つを通すためには

冷静に分岐条件を考える必要がありました。

root = stringToTreeNode("[1,-2,-3,1,3,-2,null,-1]")
Solution().printAll(root)
print("maxDepth:%s" % Solution().maxPathSum(root))

root = stringToTreeNode("[5,4,8,11,null,13,4,7,2,null,null,null,1]")
Solution().printAll(root)
print("maxDepth:%s" % Solution().maxPathSum(root))

両方ともリートコードで提出して始めてエラーになりわかった問題ですので

実装しただけでは到底きづけません。

最終的にには

self.maxi = max(self.maxi, x, max_left + max_right + node.val)

のように、左と右とノードをmaxiとしては候補にあげるが、後ろに伝えわしない

if node.val < 0:
    return max(max_left + node.val, max_right + node.val)
else:
    return x

というのが味噌である。

class Solution:
    def printAll(self, root: TreeNode):
        root.p()
    def __init__(self):
        self.maxi = -sys.maxsize - 1


    def rec(self, node: TreeNode) -> int:
        if node == None: return -sys.maxsize - 1
        max_left = self.rec(node.left)
        max_right = self.rec(node.right)
        x = max(
            node.val,
            max_left, max_right,
            max_left + node.val, max_right + node.val)
        self.maxi = max(self.maxi, x, max_left + max_right + node.val)
        if node.val < 0:
            return max(max_left + node.val, max_right + node.val)
        else:
            return x

    def maxPathSum(self, node: TreeNode) -> int:
        self.maxi = -sys.maxsize - 1
        self.rec(node)
        return self.maxi

実装後です。timespace anaylysis (時間とスペースの分析）は　n回再帰をかけるわけですが毎回単純な比較しかしてない

のでO(n)です。スペースは再帰文のo(n)です

はい！なんとか自力でとけました。

初めてのhard問題で解けたのでこれまた嬉しかったです