こんにちは
今回の学びは
・再帰でも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問題で解けたのでこれまた嬉しかったです
まとめ
再帰でもO(n)ならいい感じだよ。つまり実装してOK。
以上です