3

我的问题是用签名写一个方法

public static BinaryTree generate(BinaryTree root)

（可以添加其他参数）

此方法必须返回一个BinaryTree给定的参数（相同大小等），只需要更改其节点中的值。结果树的每个节点的值必须等于我们使用前序遍历时处理等效节点的位置root。我们从 1 开始计数。

public class BinaryTree {
    public int value;
    public BinaryTree left;
    public BinaryTree right;

    public BinaryTree(int value, BinaryTree left, BinaryTree right)
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

我尝试了以下方法，但它无法正常工作。

public static BinaryTree preOrder(BinaryTree root, int num)
{
    //We ALWAYS give 1 as num value!!
    if (root == null)
        return null;

    root.value = num;       
    preOrder(root.left, ++num);         
    preOrder(root.right, ++num);

    return root;
}

例如，如果我们有一个二叉树：

             3
         /      \
       2           1
    /     \
  1         0

（节点中有什么值并不重要！）

我们的方法必须返回这棵树：

             1
         /      \
       2           5
    /     \
  3         4
4

2 回答 2

0

对于示例树，您的代码是否返回如下内容：

      1
    /   \
   2     3
 /  \
3    4

如果是这样，您就走在了正确的轨道上，并且可能理解使用递归来访问预购节点，但您可能忘记了 int 是一种值类型！我想......我的java生锈了。无论如何，如果你可以通过引用传递 int 并且问题是我认为你应该很好。从快速的谷歌搜索看来，制作“可变 int”的简单方法是将其包装在一个单元格中，如 Ted Hopp 建议的（int [1]），或者您可以使用 MutableInt（答案的完整路径：Java：最佳方式通过引用传递 int）。

于 2013-07-30T03:16:18.017 回答
0

使用递归方法最容易做到这一点。要分配节点值，最简单的方法是使用可在所有递归级别访问的静态计数器。过程很简单：每次访问输入树中的一个节点时，在输出树中创建一个对应的节点，并将其值设置为静态计数器，然后在递归左右子树（如果存在）之前递增计数器.

通过使用静态变量而不是传递int参数（就像您在当前代码中所做的那样），在递归返回时将看到在更深层次的递归完成的增量。

如果您不想使用静态计数器（或者如果它违反规则），请使用int[1]可用于返回和传递int值的数组。

如果不清楚，我可以尝试详细说明，但我不会发布代码，因为这听起来像是学校作业。

编辑由于这不是学校作业，因此这里的代码可以满足您的要求：

public class BinaryTree {
    public int value;
    public BinaryTree left;
    public BinaryTree right;

    public BinaryTree(int value, BinaryTree left, BinaryTree right)
    {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public static BinaryTree generate(BinaryTree root) {
        // allocate a counter and delegate to the recursive method
        int[] counter = {1};
        return generate(root, counter);
    }

    /**
     * Recursive method to generate a copy of a binary tree
     * with values indicating the preorder traversal order.
     *
     * @param root
     *        the root of the tree to copy
     * @param counter
     *        an array containing the traversal order counter as its
     *        first element. On entry, it should contain the value to
     *        use for the root of the generated (sub)tree. On return,
     *        it will contain one more than the last value used.
     */
    private static BinaryTree generate(BinaryTree root, int[] counter) {
        // recursion base case
        if (root == null) {
            return null;
        }

        // capture current value and increment the counter
        int value = counter[0];
        ++counter[0];

        // generate left subtree - this will change the counter unless
        // the left subtree is null
        BinaryTree left = generate(root.left, counter);

        // generate right subtree - may change the counter
        BinaryTree right = generate(root.right, counter);

        // Complete the copy by generating the root node;
        // return the result
        return new BinaryTree(value, left, right);
    }
}
于 2013-07-30T00:46:01.860 回答