Diamètre de l’arbre binary – Meilleure conception

J’ai écrit un code pour trouver le diamètre de l’arbre binary. Besoin de suggestions pour ce qui suit:

  1. Puis-je faire cela sans utiliser de variable statique au niveau de la classe?
  2. L’algorithme est-il correct / des suggestions?

    public class DiameterOfTree { public static int diameter = 0; public static int getDiameter(BinaryTreeNode root) { if (root != null) { int leftCount = getDiameter(root.getLeft()); int rightCount = getDiameter(root.getRight()); if (leftCount + rightCount > diameter) { diameter = leftCount + rightCount; System.out.println("---diameter------------->" + diameter); } if ( leftCount > rightCount) { return leftCount + 1; } return rightCount + 1; } return 0; } } 

Il existe trois cas à prendre en compte lorsque vous essayez de trouver le chemin le plus long entre deux nœuds dans un arbre binary (diamètre):

  1. Le plus long chemin traverse la racine,
  2. Le chemin le plus long est entièrement contenu dans le sous-arbre de gauche,
  3. Le chemin le plus long est entièrement contenu dans le sous-arbre de droite.

Le plus long chemin à travers la racine est simplement la sum des hauteurs des sous-arbres gauche et droit + 1 (pour le nœud racine), et les deux autres peuvent être trouvés de manière récursive:

 public static int getDiameter(BinaryTreeNode root) { if (root == null) return 0; int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight()) + 1; int leftDiameter = getDiameter(root.getLeft()); int rightDiameter = getDiameter(root.getRight()); return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter)); } public static int getHeight(BinaryTreeNode root) { if (root == null) return 0; return Math.max(getHeight(root.getLeft()), getHeight(root.getRight())) + 1; } 

Voici une solution O (n) avec un minimum de modifications de la réponse acceptée:

 public static int[] getDiameter(BinaryTreeNode root) { int[] result = new int[]{0,0}; //1st element: diameter, 2nd: height if (root == null) return result; int[] leftResult = getDiameter(root.getLeft()); int[] rightResult = getDiameter(root.getRight()); int height = Math.max(leftResult[1], rightResult[1]) + 1; int rootDiameter = leftResult[1] + rightResult[1] + 1; int leftDiameter = leftResult[0]; int rightDiameter = rightResult[0]; result[0] = Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter)); result[1] = height; return result; } 

Il calcule simplement la hauteur et le diamètre en même temps. Et comme Java n’a pas de référence par référence, j’ai défini un int [] pour renvoyer le résultat.

Voici une solution en Java qui a une complexité temporelle O(N) . Il calcule la hauteur dans la même récursion lors du calcul du diamètre. Lien de référence

 private class HeightWrapper { int height = 0; } private int getDiameter_helper(BinaryTreeNode root, HeightWrapper wrapper) { if (root == null) { return 0; // diameter and height are 0 } /* wrappers for heights of the left and right subtrees */ HeightWrapper lhWrapper = new HeightWrapper(); HeightWrapper rhWrapper = new HeightWrapper(); /* get heights of left and right subtrees and their diameters */ int leftDiameter = getDiameter_helper(root.left, lhWrapper); int rightDiameter = getDiameter_helper(root.right, rhWrapper); /* calculate root diameter */ int rootDiameter = lhWrapper.height + rhWrapper.height + 1; /* calculate height of current node */ wrapper.height = Math.max(lhWrapper.height, rhWrapper.height) + 1; /* calculate the diameter */ return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter)); } public int getDiameter(BinaryTreeNode root) { HeightWrapper wrapper = new HeightWrapper(); return getDiameter_helper(root, wrapper); } 

Vous n’avez pas besoin de stocker le résultat dans le diamètre du champ statique. Utilisez simplement la méthode statique comme ça:

 public class DiameterOfTree { public static long getDiameter(BinaryTreeNode root) { if (root != null) { long leftDiameter = getDiameter(root.getLeft()); long rightDiameter = getDiameter(root.getRight()); long leftHeight = getHeight(root.getLeft()); long rightHeight = getHeight(root.getRight()); return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter)); } return 0; } public static long getHeight(BinaryTreeNode root) { if (root != null) { long leftHeight = getHeight(root.getLeft()); long rightHeight = getHeight(root.getRight()); return 1 + Math.max(leftHeight, rightHeight); } return 0; } } 

Le diamètre d’un arbre T est

Diamètre (T) = max (Diamètre (T. gauche), Diamètre (T. droite), Hauteur (T. gauche) + Hauteur (T. droite) +1)

  private class Data { public int height; public int diameter; } private void diameter(TreeNode root, Data d) { if (root == null) { d.height = 0; d.diameter = 0; return; } diameter(root.left, d); // get data in left subtree int hLeft = d.height; int dLeft = d.diameter; diameter(root.right, d); // overwrite with data in right tree d.diameter = Math.max(Math.max(dLeft, d.diameter), hLeft+d.height+1); d.height = Math.max(hLeft, d.height) + 1; } public int diameter(TreeNode root) { Data data = new Data(); diameter(root, data); return data.diameter; } 

Il y a une réponse minimale O (n) par rapport à la réponse acceptée.

 int DiameterTree(BinaryTreeNode root, int diameter) { int left, right; if (!root) return 0; left = DiameterTree(root.getLeft(), diameter); right = DiameterTree(root.getRight(), diameter); if (left + right > diameter) diameter = left + right; return Math.max(left, right) + 1; } 

Supposons que le diameter est une variable statique dans la classe.

 public class NodeWrap{ int height = 0; int maxLength = 0; public NodeWrap(int h, int m){ height = s; maxLength = m; } } public NodeWrap getDiameter(BinaryNode root){ if(root == null){ return new NodeWrap(0, 0); } NodeWrap left = getDiameter(root.left); NodeWrap right = getDiameter(root.right); int height = Math.max(left.height + right.height) + 1; int maxLength = Math.max(left.maxLength, right.maxLength); if(left.height != 0 && right.height != 0){ maxLength = Math.max(left.height + right.height + 1, maxLength); } return new NodeWrap(singleLength, maxLength); } 

Solution soignée et propre:

 // way to use below util function: prop p = new prop(); diameterUtil(root, p); System.out.println(pd); class prop { int h; int d; } private void diameterUtil(Node n, prop p) { if (n == null) { ph = 0; pd = 0; return; } prop lp = new prop(); prop rp = new prop(); diameterUtil(n.left, lp); diameterUtil(n.right, rp); ph = Math.max(lp.h, rp.h) + 1; pd = Math.max((lp.h + rp.h + 1), Math.max(lp.d, rp.d)); } 

Voici une solution récursive en C ++ qui vous donne la hauteur ainsi que le diamètre de l’arbre binary.

 struct tree { int height = -1; int diameter = 0; }; struct tree BSTDiameter(struct node *root) { struct tree currentTree, leftTree, rightTree; if (root == NULL) { currentTree.height = -1; currentTree.diameter = 0; return currentTree; } leftTree = BSTDiameter(root->left); rightTree = BSTDiameter(root->right); currentTree.height = ((leftTree.height > rightTree.height) ? leftTree.height : rightTree.height) + 1; if (leftTree.height == -1 || rightTree.height == -1) currentTree.diameter = 0; else currentTree.diameter = (leftTree.height + rightTree.height + 3) > (rightTree.diameter > leftTree.diameter ? rightTree.diameter : leftTree.diameter) ? (leftTree.height + rightTree.height + 3) : (rightTree.diameter > leftTree.diameter ? rightTree.diameter : leftTree.diameter); return currentTree; } 

La complexité temporelle de ceci est O (h) où h est la hauteur de l’arbre. J’espère que cela vous a aidé.