Finding the largest sum of disjoint leaf-to-leaf paths in a binary tree-CodePudding

I need advice on a task where I am looking for disjoint paths leading from leaf to leaf (they must not return along the same path/edge) so that their sum creates the greatest possible value, i.e. the paths must not intersect and must be as good as possible belongs to the total. And be careful, the point (root) where the path breaks is not included in the total sum, viz. picture.

I don't know how to solve the problem at all. I am attaching code that tries to decide whether to choose a path by one leaf or to choose a smaller subtree, but it does not work correctly.

If anyone has any study material I would be very grateful. Thank you in advance All program

I was unable to create an algorithm to solve the problem. I would like some advice, study materials that I could use in the solution.

CodePudding user response：

Let's call the function, f, our overall task, with input parameter a root to a tree. Let's call the function, g, the maximum continuously descending path from a given node, including the node, that also adds the result of f for each node not chosen.

Starting at the root of the tree, in a run of f, for each node, we can either assign it (1) as a parent in a path, or (2) not part of any path. In the case of (1), we'd like g(left_child) g(right_child). In the case of (2), we'd like f(left_child) f(right_child).

Python code with your second example, where the root is not part of any path:

def g(tree):
  if tree == None:
    return 0
  return tree["val"]   max(
    g(tree["l"])   f(tree["r"]),
    g(tree["r"])   f(tree["l"])
  )

def f(tree):
  if tree == None:
    return 0
  return max(
    g(tree["l"])   g(tree["r"]),
    f(tree["l"])   f(tree["r"])
  )
  
tree = {
  "val": 0,
  
  "l": {
    "val": 2,
    
    "l": {
      "val": 2,
      "l": None,
      "r": None
    },
    
    "r": {
      "val": 3,
      "l": None,
      "r": None
    }
  },
  
  "r": {
    "val": 1,
    
    "l": {
      "val": 2,
      "l": None,
      "r": None
    },
    
    "r": {
      "val": 3,
      "l": None,
      "r": None
    }
  }
}

print(f(tree)) # 10

Your third example:

tree = {
  "val": 0,
  
  "l": {
    "val": 6,
    
    "l": {
      "val": 5,
      "l": None,
      "r": None
    },
    
    "r": {
      "val": 3,
      "l": None,
      "r": None
    }
  },
  
  "r": {
    "val": 5,
    
    "l": {
      "val": 7,
      
      "l": {
        "val": 3,
        "l": None,
        "r": None
      },
    
      "r": {
        "val": 6,
        "l": None,
        "r": None
      }
    },
    
    "r": {
      "val": 7,
      
      "l": {
        "val": 6,
        "l": None,
        "r": None
      },
    
      "r": {
        "val": 7,
        "l": None,
        "r": None
      }
    }
  }
}

print(f(tree)) # 42