0

現在、並べ替えられたリンク リストがあり、void リターン メソッドを使用して、リスト (2 番目のパラメーターと呼ばれます) からバランスのとれた二分探索木を再帰的に構築する必要があります。パラメータとして、LL ヘッド、作成されるルート、およびリストの長さのみを指定できます。

このメソッドは LL に対して破壊的であってはならず、後でツリーをテストするために、printTree と treeDepth があります。

public static void makeBalancedTree(ListNode head, TreeNode root, int count)
{
    //here
}
public static void printTree(TreeNode root)
{
    if(root != null)
    { 
        //Print recursive left, center, recursive right
        printTree(root.left);
        System.out.print(root.data + " ");
        printTree(root.right);
    }   
}

public static int depth(TreeNode root)
{
    if (root == null)
        return -1;

    int deep;
    //Return larger of the two subtree's depths, +1
    deep = Math.max(depth(root.right), depth(root.left));
    return deep+1;
    }
public static int countList(ListNode head)
    {

        int count = 0;

        ListNode cursor = new ListNode();
        cursor = head;

        while (cursor.link != null)
        {
            cursor = cursor.link;
            ++count;
        }
        return count;

    }
4

1 に答える 1

0

Java を指定しましたが、宿題の解決策を書くつもりはないので、Ruby での実用的な解決策を次に示します。

class TreeBuilder
  attr_reader :root    # generate root instance var and getters

  # Constructor.  Initially the tree is empty.
  def initialize
    @root = nil
  end

  # This is the public front-end for building a binary tree from an
  # iterable set.  It invokes a recursive back-end.  
  def buildTree(aList)
    aList.sort!      # ensure list is sorted, delete this if you trust input
    # Hand the recursive back end an iterator and the initial list size,
    # make the returned result the root of the tree.
    @root = __build_tree__(aList.each, aList.size)
  end

  # Autocreate a Node class as a structure with a payload and
  # left and right subtree references.  This automagically has
  # setters and getters with the same name as the instance vars.    
  Node = Struct.new(:payload, :left, :right)

  # Recursive back end attempts to build subtrees.
  # This takes an Enumerator (Iterator if you prefer) for the
  # linked list, the current depth of this attempt (which is
  # how balance is maintained), and returns a Node reference.    
  def __build_tree__(list_enum, depth)
    if depth > 0      # If we're not too deep in the tree for balance...
      # Try constructing the left subtree first
      left = __build_tree__(list_enum, depth / 2)
      # Now for the current Node...
      # The begin/rescue block corresponds to a Java if/else check
      # on whether the Iterator "hasNext()".  Java can pre-check,
      # Ruby says "Just try getting the next value and catch the
      # exception if it's not there"
      begin
        # Try getting the next value from the linked list
        value = list_enum.next
      rescue StopIteration
        # If we ran out of values, bail out with just the "left" subtree
        return left
      end
      # If we succeeded in getting a value, construct the Node to store
      # it in, populate its left subtree, and try building and populating
      # the right subtree as well.
      return Node.new(value, left, __build_tree__(list_enum, (depth-1) / 2))
    end
    # Recursive base case - if we kept going, the tree would end up unbalanced
    return nil
  end
end

上で述べたように、これは Ruby で実際に動作するコードです。これを割り当てにマップするのはあなた次第ですが、リストを反復処理し、各要素を適切な場所に配置してバランスの取れたツリーになるようにするための基本的なロジックが含まれています。

于 2015-04-27T13:41:11.433 に答える