二叉树直径 – 更好的设计
我写了一个代码来查找二叉树的直径。 需要以下建议：
- 我可以不在类级别使用静态变量吗？
-
算法是罚款/任何建议？
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; } }
尝试在二叉树（直径）中找到两个节点之间的最长路径时，需要考虑三种情况：
- 最长的路径穿过根，
- 最长的路径完全包含在左子树中，
- 最长的路径完全包含在右子树中。
通过根的最长路径只是左和右子树的高度之和+ 1（对于根节点），其他两个可以递归地找到：
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; }
这是一个O（n）解决方案，对接受的答案进行了微小的更改：
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; }
它只是同时计算高度和直径。 由于Java没有pass-by-reference，我定义了一个int []来返回结果。
这是Java中具有O(N)时间复杂度的解决方案。 它在计算直径时计算相同递归的高度。 参考链接
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); }
您不需要将结果存储在静态字段直径中。 只需使用这样的静态方法：
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; } }
树T的直径是
直径（T）=最大（直径（T.left），直径（T.right），高度（T.left）+高度（T.right）+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; }
与接受的答案相比，存在最小的O（n）答案。
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; }
假设diameter是类中的静态变量。
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); }
整洁干净的解决方案：
// 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)); }
这是C ++中的一个递归解决方案，它为您提供二叉树的高度和直径。
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; }
其时间复杂度为O（h），其中h是树的高度。 希望对你有所帮助。