Início / coding / Perguntas / 78894002
Accepted
ABGR
Asked: 2024-08-21 02:45:25 +0800 CST

Diâmetro de uma árvore binária - caso de falha quando o caminho mais longo não passa pela raiz

  • 772

Então, estou trabalhando neste problema :

Dada a raiz de uma árvore binária, retorne o comprimento do diâmetro da árvore.

O diâmetro de uma árvore binária é o comprimento do caminho mais longo entre quaisquer dois nós de uma árvore. Este caminho pode ou não passar pela raiz.

O comprimento de um caminho entre dois nós é representado pelo número de arestas entre eles.

Veja como tentei resolver:

var diameterOfBinaryTree = function(root) {

  if (root === null) return 0;
  let max_height = 0;

  function maxDepth(node) {
    if (node === null) return 0;
    var lh = maxDepth(node.left);
    var rh = maxDepth(node.right);

    return 1 + Math.max(lh, rh);
  }

  max_height = Math.max(max_height, maxDepth(root.left) + maxDepth(root.right));

  diameterOfBinaryTree(root.left);
  diameterOfBinaryTree(root.right);

  return max_height
}

Agora, isso funciona, exceto aparentemente no caso em que o caminho mais longo não passa pelo nó raiz. Mas tentei incorporar esses casos, ou seja, itero em cada nó da árvore:

diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);

Onde estou errando? Agradeço qualquer ajuda. Observe que preciso otimizar isso de O(N2) para O(N), mas por enquanto estou apenas tentando a força bruta.

O caso de teste para o qual falha é esta árvore:

insira a descrição da imagem aqui

Considere o caminho mais longo nas passagens de -1 a -2

javascript

2 respostas

  1. Best Answer

    Mas tentei incorporar esses casos, ou seja, itero em cada nó da árvore:

    diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);

    Onde estou errando?

    A diameterOfBinaryTreefunção realiza um cálculo e retorna um valor, mas não tem nenhum "efeito colateral" — na verdade, não faz nada — então nunca há motivo para chamá-la e descartar seu resultado. E isso é uma coisa boa! Funções puras como esta são mais fáceis de raciocinar (tanto para humanos quanto para compiladores). Mas isso significa que essas chamadas recursivas são inúteis.

    Em vez disso, você precisa realmente usar o resultado:

    return Math.max(
    maxDepth(root.left) + maxDepth(root.right),
    diameterOfBinaryTree(root.left),
    diameterOfBinaryTree(root.right)
);
    • 3

  2. Você precisa começar a percorrer a partir da raiz e, em seguida, calcular o valor máximo do diâmetro do diâmetro atual e a adição de esquerda + direita na iteração do nó em que você está.

    function diameterOfBinaryTree(root) {
    let max_height = 0;
    
    function maxDepth(node) {
        if (!node) return 0;// if our node is falsy, means no path anymore, return 0

        // Assign the left  of tree to leftHeight and right of tree to rightHeight
        const leftHeight = maxDepth(node.left); 
        const rightHeight = maxDepth(node.right);

        // take the max of current diameter and combination of left+right (in case path goes through root)
        max_height = Math.max(diameter, leftHeight + rightHeight);
        return Math.max(leftHeight, rightHeight) + 1; // add 1 to go a level above
    }
    maxDepth(root); // begin traversing from root
    return max_height;
}
    • -1

relate perguntas