java - 二分木の直径-より良い設計

Question

二分木の直径を見つけるためのコードを書きました。次の提案が必要です。

クラスレベルで静的変数を使用せずにこれを行うことはできますか？

アルゴリズムは問題ありませんか/何か提案はありますか？

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;
  }
}

score 42 · Accepted Answer

二分木（直径）内の2つのノード間の最長パスを見つけようとするときに考慮すべき3つのケースがあります。

最長のパスはルートを通過し、
最長のパスは完全に左側のサブツリーに含まれています。
最長のパスは完全に右側のサブツリーに含まれています。

ルートを通る最長のパスは、単純に左右のサブツリーの高さの合計です（ルートノードと1つの左、1つの右のサブツリーノードを持つツリーの直径は2になるため、ルートの+1は不要です。）、および他の2つは再帰的に見つけることができます：

public static int getDiameter(BinaryTreeNode root) {        
    if (root == null)
        return 0;

    int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight()); //Removing the +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;
}

score 41 · Accepted Answer

受け入れられた回答への変更を最小限に抑えた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には参照渡しがないため、結果を返すint[]を定義しました。

score 9 · Accepted Answer

O(N)これは、時間計算量のあるJavaのソリューションです。直径を計算するときに、同じ再帰で高さを計算します。参照リンク

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);
}

score 4 · Accepted Answer

結果を静的フィールドの直径に保存する必要はありません。次のような静的メソッドを使用するだけです。

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;
    }
}

score 3 · Accepted Answer

受け入れられたものと比較して最小限の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クラス内の静的変数であると仮定します。

score 2 · Accepted Answer

木の直径Tは

Diameter（T）= max（Diameter（T.left）、Diameter（T.right）、Height（T.left）+ Height（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;  
 }

score 1 · Accepted Answer

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);
}

score 1 · Accepted Answer

One more O(n) solution in python,
code is self explanatory, only issue with this code is it returns tuple containing both height and diameter of the tree. 

def diameter(node, height):
  if node is None:
    return 0, 0
  leftheight  = 0
  rightheight = 0
  leftdiameter,  leftheight = diameter(node.left, leftheight)
  rightdiameter, rightheight = diameter(node.right, rightheight)
  rootheight = 1 + max(leftheight, rightheight ) 
  rootdiameter = ( leftheight + rightheight + 1 )
  return max( rootdiameter, leftdiameter, rightdiameter ), rootheight

score 0 · Accepted Answer

きちんとしたクリーンなソリューション：

// way to use below util function:
prop p = new prop();
diameterUtil(root, p);
System.out.println(p.d);

class prop {
    int h;
    int d;
}

private void diameterUtil(Node n, prop p) {
    if (n == null) {
        p.h = 0;
        p.d = 0;
        return;
    }
    prop lp = new prop();
    prop rp = new prop();
    diameterUtil(n.left, lp);
    diameterUtil(n.right, rp);
    p.h = Math.max(lp.h, rp.h) + 1;
    p.d = Math.max((lp.h + rp.h + 1), Math.max(lp.d, rp.d));
}

score 0 · Accepted Answer

これは、二分木の高さと直径を提供するC++の再帰的ソリューションの1つです。

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は木の高さです。それがあなたを助けたことを願っています。

score 0 · Accepted Answer

最も効率的な方法は、直径と高さを計算してO（n）に到達することです。これを取得する最も簡単な方法は、[Python3、PyPy3]です。

for this definition for a binary tree node,
class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
    self.height = 1

    def height(node):
        if node is None:
            return 0
        l_height = height(node.left)
        r_height = height(node.right)
        self.height = max(self.height,l_height+r_height+1)
        return max(l_height,r_height) + 1

    height(root)
    return self.height-1

実行時間が速く、複雑さが少ない、最もシンプルで手頃なソリューション。

java - 二分木の直径-より良い設計

11 に答える 11

Related

Reference