java - 最大轨迹二叉树

Question

-- java -- 对于树

     5
  4     3
30  5     

我需要找到“最大轨道”，所以对于这棵树，它的 39 (5​​+4+30)

我需要一个可以做到这一点的函数（复杂度 O（n））有人可以帮助我吗？

public static int GetTreePath(BinTreeNode<Integer> t){
        if (t==null)
            return 0;

        if (t.IsLeve()){
            return t.getInfo();
        }else{
            GetTreePath(t.getLeft());
            GetTreePath(t.getRight());
        }
        return t.getInfo();
    }

Answer 1

有一个DP解决方案。

F(i) = max(F(child) + value(i))

calculate(f)从叶子到根，或递归并保存f(i)

Answer 2

只需稍微修改您的代码，以获得两个可能的子树的最大值。

public static int GetTreePath(BinTreeNode<Integer> t){
    if (t==null)
        return 0;

    if (t.IsLeve()){
        return t.getInfo();
    }else{
        return Math.max(
            GetTreePath(t.getLeft()), 
            GetTreePath(t.getRight()) 
            ) + t.getInfo();
    }
}