0

我目前有一个排序的链表，并且使用void返回方法，我需要从列表中递归构造一个平衡的二叉搜索树（称为第二个参数）。作为参数，我只能有 LL Head、正在创建的根和列表的长度。

该方法不会对 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 回答