algorithm - 在二叉树中找到最大的不相交叶到叶路径之和

Question

我需要一个任务的建议，我正在寻找从一个叶子到另一个叶子的不相交路径(它们不能沿着相同的路径/边缘返回)，以便它们的总和创造最大可能的值(value)，即路径不能相交并且必须尽可能好地属于总。请注意，路径中断的点(根)不包括在总和中，即。图片。

完全不知道怎么解决这个问题。我附上的代码试图决定是选择一片叶子的路径还是选择一个较小的子树，但它无法正常工作。

如果谁有任何学习资料，我将不胜感激。先感谢您 所有程序 https://onecompiler.com/c/3ymb7xvzn

int depth(struct node *root, int *res)
{
    if(root == NULL) return 0;
    
    int l = depth(root->left, res);
    int r = depth(root->right, res);
    
    int max_single_best_Way = max(l+root->data, r+root->data);

    int max_root = l+r;
    
    int maximum = max(max_single_best_Way, max_root);
    *res = max(*res, maximum);

    return maximum;

}

我无法创建算法来解决问题。我想要一些可以在解决方案中使用的建议和学习 Material 。

Answer 1

让我们调用函数f，这是我们的总体任务，输入参数是树的根。让我们调用函数 g，它是从给定节点(包括该节点)开始的最大连续下降路径，它还为每个未选择的节点添加 f 的结果。

从树的根开始，在 f 的运行中，对于每个节点，我们可以将其分配 (1) 作为路径中的父节点，或者 (2) 不是路径的一部分任何路径。在 (1) 的情况下，我们想要 g(left_child) + g(right_child)。在 (2) 的情况下，我们想要 f(left_child) + f(right_child)。

第二个示例的 Python 代码，其中根目录不属于任何路径:

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

你的第三个例子:

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