java - 根据前序遍历返回二叉树的方法

Question

我遇到的问题是写一个带有签名的方法

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

Answer 1

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

      1
    /   \
   2     3
 /  \
3    4

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