이진 트리의 최대 경로 합을 찾는 방법

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 코드의 첫 번째 예에서 루트 노드는 최대 경로를가집니다. 두 번째 예에서 하위 경로는 최대 합계를가집니다.

참고 문헌 :

Wikipedia Binary Tree

최근 댓글