どのように出力が7でなければなりません。ここバイナリツリー

Question

import java.util.*; 

class Node 
{ 
    int data; 
    Node left , right; 
    public Node (int item) 
    { 
     data = item; 
     left = right = null; 
    } 
} 

class BinaryTree 
{ 
    public static Node root; 
    BinaryTree() 
    { 
     root = null; 
    } 

    public int largestBST(Node root) 
    { 
       MinMax m = largest(root); 
      return m.size; 
    } 

    public MinMax largest(Node root) 
    { 
     if(root == null) 
     { 
      return new MinMax(); 
     } 

     MinMax leftMinMax = largest(root.left); 
     MinMax rightMinMax = largest(root.right); 

     MinMax m = new MinMax(); 

     if(leftMinMax.isBST == false || rightMinMax.isBST == false || (leftMinMax.max > root.data) || (rightMinMax.min <= root.data)) 
     { 
      m.isBST = false; 
      m.size = Math.max(leftMinMax.size , rightMinMax.size); 
     } 

     m.isBST = true; 
     m.size = leftMinMax.size + rightMinMax.size + 1; 

     m.min = root.left != null ? leftMinMax.min : root.data;//if left node is null take node as min or min of left 

     m.max = root.right != null ? rightMinMax.max : root.data;//if right node is null take node as max or max of right 

     return m; 
    } 

    class MinMax 
    { 
     int max,min; 
     boolean isBST; 
     int size; 
     MinMax() 
     { 
      max = Integer.MIN_VALUE; 
      min = Integer.MAX_VALUE; 
      isBST = false; 
      size = 0; 
     } 
    } 

    public static void main(String args[]) 
    { 
     BinaryTree bt = new BinaryTree(); 
     bt.root = new Node(25); 
     bt.root.left = new Node(18); 
     bt.root.right = new Node(50); 
     bt.root.left.left = new Node(19); 
     bt.root.left.right = new Node(20); 
     bt.root.right.left = new Node(35); 
     bt.root.right.right = new Node(60); 
     bt.root.right.left.right = new Node(40); 
     bt.root.right.left.left = new Node(20); 
     bt.root.right.right.left = new Node(55); 
     bt.root.right.right.right = new Node(70); 

     int size = bt.largestBST(root); 

     System.out.println("The size of largest BST is " + size); 
    } 
} 

で最大のBSTのサイズを見つけることではなく、それは、ツリー内のノードの合計数を示している、すなわち11コードと間違って何

？

Answer 1

あなたは、このようなlargestBST(Node root)がどうなるの書き換え、ツリーの最大の深さを発見したい場合：

public int largestBST(Node root) 
{ 
    if (root == null) { 
     return 0; 
    } 

    return 1 + Math.max(largestBST(root.left), largestBST(root.right)); 
} 

ここで何が起こっているが、我々は1 + max(left subtree depth, right subtree depth)を返すということです。ノードが存在しない場合は、0を返して再帰を停止します。これは4を返します。 、

public int largestBST(Node root) 
{ 
    if (root == null) { 
     return 0; 
    } 

    return Math.max(countNodes(root.left), countNodes(root.right)); 
} 

public int countNodes(Node root) 
{ 
    if (root == null) { 
     return 0; 
    } 

    return 1 + countNodes(root.left) + countNodes(root.right); 
} 

あなたが見ることができるように：最大によって、あなたは関係なく、深さの、与えられたルートから始まるほとんどのノードとのサブツリーを意味する場合

は、我々は次取得するには、このソリューションを変更することができます再帰はcountNodes()メソッドで行われ、largestBST()は左と右の枝からmaxを返します。再帰は前と同じ原則に従います。ノードが存在しない場合は0が返され、存在する各ノードに1が追加されます。結果は7になります。