Como encontrar a soma do caminho máximo de uma árvore binária

12/05/2018

Este é um bom exemplo de recursão. O algoritmo precisa processar todos os nós. Se a soma de cada sub-árvore for maior que o máximo atual, armazenamos o máximo. O algoritmo está em o (n) onde n é o número de nós.

Crie o seguinte arquivo java:

public class InterviewBTreeMaximumPathSum {

    int max = 0;
    
    public int maxPathSum(TreeNode a) {
	// Validação de entrada
	if( a == null )
	    throw new IllegalArgumentException( "Resultado:" );
	
	max = 0;

	// Processar o nó
	maxPathSumNode(a);
	
	// Retornar o valor máximo
	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("Entrada:" + in.toString());
	System.out.println("Resultado:" + 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("Entrada:" + in.toString());
	System.out.println("Resultado:" + 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; 
    }
}

O resultado será:

Entrada:(value=1, left=(value=2), right=(value=3) )
Resultado:6
Entrada:(value=1, left=(value=1, left=(value=1), right=null ), right=(value=2, left=(value=5), right=(value=3) ) )
Resultado:10

No primeiro exemplo do código java, o nó raiz tem o caminho máximo. No segundo exemplo, um sub-caminho tem a soma máxima.

Referências:

Wikipedia Binary Tree

Comentários Recentes