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

只需稍微修改一下代码即可获得两个可能的子树的最大值。

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();
    }
}