方法，根据前序遍历返回二叉树

我的问题是写一个方法与签名方法，根据前序遍历返回二叉树

public static BinaryTree generate(BinaryTree root)

（有可能增加其他参数）

这种方法必须返回一个BinaryTree像作为参数给定（相同大小等），只需要改变其节点中的值。当我们使用root上的前序遍历时，生成的树的每个节点的值必须等于等效节点的处理位置。我们从1开始计数。

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

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; 
}

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

（不要紧，有集中的节点什么值！）

我们的方法必须返回此树：

来源

2013-07-30 OxomHuK

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

通过使用静态变量而不是传递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-30 00:46:01

谢谢你的回答。它不是一个真正的学校作业，我只是想自己解决这个问题，但可能我不够聪明。你能解释我什么是静态柜台吗？那么可以用来返回的int [1]数组是什么意思？ – OxomHuK

Ouu，Ive通过int [1]使用该技巧来修复它。谢谢！！！！家伙 – OxomHuK

@OxomHuK - 我添加了我的代码版本。 –

对于例如独木代码返回是这样的：

如果是这样你在正确的轨道上，并可能理解使用递归来访问节点，但你可能已经忘记了int是一个值类型！我认为......我的Java很生疏。无论如何，如果你可以通过引用传递整数，问题就是我认为的那样，你应该是好的。从一个快速的谷歌搜索它看起来像一个简单的方法来使一个“可变的整数”是将其包装在一个单元格，如Ted Hopp建议（int [1]），或者你可以使用MutableInt（完整路径的答案：Java : Best way to pass int by reference）。

来源

2013-07-30 03:16:18 Teeknow

方法，根据前序遍历返回二叉树

回答

相关问题