tópico:
Soma do caminho máximo da árvore binária
Dada uma árvore binária, encontre a soma máxima do caminho.
O caminho pode começar e terminar em qualquer nó na árvore.
Por exemplo:
Dada a árvore binária abaixo,
1 / / 2 3
Retornar 6.
O nó pode ser negativo, procurando o máximo de caminho para que os nós passados sejam os maiores. O caminho pode começar e terminar em qualquer nó, mas não pode voltar.
Embora essa pergunta pareça incomum, se você pensar bem, você descobrirá que nada mais é do que travessia de árvores binárias + idéias de planejamento dinâmico simples.
Podemos separar o problema: mesmo que o último maior caminho não passe pelo nó raiz, ele deve ter seu próprio "ponto mais alto". Portanto, precisamos descobrir apenas para todos os nós: se o caminho toma esse nó como o "ponto mais alto", qual é o comprimento máximo do caminho? Nota como máx. Em seguida, encontre o valor máximo máximo no máximo, que é o resultado que você está procurando. A mesma idéia que "encontrar a maior subsequência contínua em uma sequência inteira".
O seguinte é encontrar a relação entre o máximo correspondente a cada "ponto mais alto".
Vamos tomar o nó raiz como exemplo. O método de cálculo para o caminho máximo que passa pelo nó raiz é:
Encontramos o comprimento do caminho máximo A na subárvore esquerda com a criança esquerda como ponto de partida e o comprimento do caminho máximo B na subárvore direita com a criança direita como ponto de partida. Então o max = max deste ponto (a+b+node.val, a+node.val, b+node.val, node.val)
Portanto, definimos uma função para calcular A ou B acima. Seu parâmetro é um nó e seu valor de retorno é o comprimento do caminho máximo. No entanto, o ponto de partida desse caminho deve ser o nó de entrada, e o caminho deve estar em uma subárvore com o ponto de partida como o nó raiz.
Em seguida, o valor de retorno da função func (nó) pode ser definido da seguinte forma: returnmax (func (node.left)+node.val, func (node.right)+node.val, node.val)
A condição de terminação é nó == nulo e retorna 0 diretamente.
Em seguida, descobrimos que o processo acima do cálculo do máximo e do cálculo do max pode ser completamente colocado em func (nó).
De acordo com o código dessa idéia, o MaxPathSumcore é a implementação acima do FUNC (NODE):
/** * Definição para árvore binária * Struct Treenode { * int val; * Treenode * à esquerda; * Treenode * à direita; * Treenode (int x): val (x), esquerda (nulo), direita (nula) {} *}; */classe Solução {public: int maxPathSum (Treenode *root) {maxPathSumcore (root); retorna max;} int maxpathSumcore (Treenode *node) {if (null == node) retornar 0; int a = maxPathore (node -> deixado); int b = b ==) à direita); if ((a+b+node-> val)> max) max = (a+b+node-> val); if ((a+node-> val)> max) max = (a+node-> val); se ((b+node-> val)> max) max = (b+node-> val); maxViaThisNode = ((a + node->val) > node->val ? (a + node->val) : node->val);return (maxViaThisNode > (b + node->val) ? maxViaThisNode : (b + node->val));}private: int MAX= -99999999;};Complexidade do tempo O (n), n é o número total de nós.
Resumir
O exposto acima é o conteúdo inteiro deste artigo sobre a análise de código do caminho máximo da árvore binária na programação Java. Espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!