Pythonでノードと子孫の違いを見つけるプログラム

二分木があるとすると、ノードとその子孫の間で最大の絶対差を見つける必要があります。

したがって、入力が次のような場合

その場合、最大の絶対差はノ​​ード8と1の間であるため、出力は7になります。

これを解決するには、次の手順に従います-

• 関数dfs（）を定義します。これはノードを取ります
• ノードがnullでない場合、
  • 正と負の無限大のリストを返す
• left：=dfs（ノードの左側）
• right：=dfs（ノードの右）
• res：=（left [0]、right [0]の最小値とノードの値、およびleft [1]、right [1]とノードの値の最大値）とのペア
• ans：=ansの最大値（ノードの値-res [0]）および（res [1]-ノードの値）
• return res
• メインの方法から、次の手順を実行します-
• ans：=0
• dfs（root）
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      def dfs(node):
         if not node:
            return [float("inf"), float("-inf")]
         left = dfs(node.left)
         right = dfs(node.right)
         res = [min(left[0], right[0], node.val), max(left[1], right[1], node.val)]
         self.ans = max(self.ans, node.val - res[0], res[1] - node.val)
         return res
      self.ans = 0
      dfs(root)
      return self.ans
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(5)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(8)
root.right.left.left = TreeNode(7)
root.right.left.right = TreeNode(4)
print(ob.solve(root))

入力

root = TreeNode(1)
root.left = TreeNode(5)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(8)
root.right.left.left = TreeNode(7)
root.right.left.right = TreeNode(4)

出力

7