バイナリツリーの最大パスの合計を見つける方法

12/05/2018

これは再帰の良い例です。 アルゴリズムはすべてのノードを処理する必要があります。 各サブツリーの合計が現在の最大値より大きい場合、最大値を格納します。 アルゴリズムはo（n）にあり、nはノードの数です。

次のJavaファイルを作成します。

public class InterviewBTreeMaximumPathSum {

    int max = 0;
    
    public int maxPathSum(TreeNode a) {
	// 입력 유효성 검사
	if( a == null )
	    throw new IllegalArgumentException( "結果：" );
	
	max = 0;

	// ノードを処理する
	maxPathSumNode(a);
	
	// 最大値を返します。
	return max;
    }

    public int maxPathSumNode(TreeNode a) {
	if( a == null )
	    return 0;
	
	int left = maxPathSumNode(a.left);
	int right = maxPathSumNode(a.right);
	
	int tmpMax = left + right + a.val;
	
	if( tmpMax > max )
	    max = tmpMax;
	
	if( left > right )
	    return left + a.val; 
	
	return right + a.val;
    }

    public static void main(String[] argv) throws Exception {
	InterviewBTreeMaximumPathSum t = new InterviewBTreeMaximumPathSum();

	TreeNode in = new TreeNode(1);
	in.left = new TreeNode(2);
	in.right = new TreeNode(3);

	int res = t.maxPathSum(in);

	System.out.println("入力：" + in.toString());
	System.out.println("結果：" + res);
	
	
	in = new TreeNode(1);
	in.left = new TreeNode(1);
	in.left.left = new TreeNode(1);

	in.right = new TreeNode(2);
	in.right.left = new TreeNode(5);
	in.right.right = new TreeNode(3);
	
	res = t.maxPathSum(in);

	System.out.println("入力：" + in.toString());
	System.out.println("結果：" + res);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
	val = x;
    }
    
    public String toString(){
	String toReturn = "(value=" + String.valueOf(val);
	if( left != null || right != null )
	    toReturn = toReturn + ", left=" + left + ", right=" + right + " ";
	toReturn = toReturn + ")";
	
	return toReturn; 
    }
}

出力は次のようになります。

入力：(value=1, left=(value=2), right=(value=3) )
結果：6
入力：(value=1, left=(value=1, left=(value=1), right=null ), right=(value=2, left=(value=5), right=(value=3) ) )
結果：10

Javaコードの最初の例では、ルートノードに最大パスがあります。 第2の例では、サブパスは最大合計を有する。

参考文献：

Wikipedia Binary Tree

最近のコメント