3

我希望这是一个可以接受的问题。我理解递归的思维模式，我想先考虑基本案例，然后再考虑递归案例，但是对于一些更困难的 BST 问题，我只是空白，感觉就像在没有好的方向的情况下迷失了方向。

以链表为例，似乎有一种解决问题的模式，但 BT 似乎你知道或不知道。任何提示/指针？我似乎已经理解的唯一概念是，如果我正在处理空节点并且我想对它们或关于它们做些什么，我会把它作为一个案例

if(root == null)
     //do something

或者如果我与空节点没有任何关系，那么我使用倒置的基本情况

if(root != null)
     //do stuff
else 
     //do nothing for null case

但即便如此，我也会不知所措。我想这是一个我被困住并且不知道如何解决的问题的例子。我不一定要寻找答案，只是处理此类问题（和常规二叉树问题）的潜在策略。

编写一个方法numberNodes来更改存储在二叉树中的数据，将从 1 开始的顺序整数分配给每个节点，以便前序遍历将产生按顺序（1、2、3 等）的数字。例如，给定由左下方的树引用的树，调用tree.numberNodes();将覆盖现有数据，将节点值从 1 分配到 6，以便树的前序遍历将产生1, 2, 3, 4, 5, 6。

你不要改变树的结构。您只是更改存储在数据字段中的值。您的方法应该返回树中有多少节点的计数。

假设您要将此方法添加到IntTree如下定义的类中：

 public class IntTree {
     private IntTreeNode overallRoot;
     ...
 }

再看一遍代码后，我想我应该用我int count的方法来确定我是去左根还是右根，因为它是一个二叉搜索树，但我仍然无法实现这个功能......啊编码堵塞！

4

4 回答 4

13

当考虑使用二叉树进行递归时，基本情况是一棵空树，所以你在正确的轨道上。另一个关键概念元素是考虑根、左子树和右子树（其中任何一个都可能为空）。

所以我会像这样分解你的示例问题：

  • 如果树是空的，则无事可做
  • 否则，将下一个数字分配给根（啊哈！-我需要将“下一个数字”传递给此方法。）
  • 在左子树上递归，比当前数字多传递一个。
  • 在右子树上递归，通过 . . . 啊。我需要知道左子树处理后的下一个数字是多少。因此，我需要调用左子树来返回下一个数字（比分配的最后一个数字多一个）。这意味着我最好做同样的事情。这将是在右子树上递归后返回的数字。
  • 当我在根节点上调用此方法时，它将在设置所有值后返回下一个可用数字。设置的节点数将比此少一。
  • 实际上，最好只返回最后使用的数字，而不是下一个可用的数字。然后我不需要一个单独的函数来从结果中减去一个。所以我最好修改前面的分析，说要传入方法的数字（以及返回的数字）应该是最后使用的数字（不是下一个可用的数字），并相应地调整所有处理。

有了这个，你几乎有了这个方法的大纲。我会这样写：

public class IntTree {
    private IntTreeNode overallRoot;

    public int numberNodes() {
        return numberNodes(overallRoot, 0);
    }

    /** Helper function */
    private static int numberNodes(IntTreeNode node, int n) {
        if (node != null) {
            node.data = ++n; // preorder means we assign to node first
            n = numberNodes(node.left, n);
            n = numberNodes(node.right, n);
        }
        return n;
    }
}
于 2013-08-22T02:59:40.400 回答
2

首先，没有空节点。可以为空的是right和left指针/引用。

其次，有许多不同类型的二叉树。我的意思是本质上不同。这就是你看不到太多共性的原因之一。

public class BTNode {
    int value;
    BTNode left;
    BTNode right;
}

public static int enumerate(BTNode startNode,int startNumber) {
    int currentNumber= startNumber ;
    if( startNode == null ) return currentNumber ;
    startNode.value= currentNumber ;    // also currentNumber++ and delete next instruction
    currentNumber++;
    currentNumber= enumerate(startNode.left,currentNumber) ;
    currentNumber= enumerate(startNode.right,currentNumber) ;    //  also together with return
    return currentNumber ;
}

计数与节点的值无关。这仅与他们的立场有关。左或右才是最重要的。

于 2013-08-22T03:02:49.800 回答
2

一般 - 画出它，编写你的 Node 类并完成你需要做的事情

在这种情况下，有几个步骤，您基本上需要对其进行逆向工程。

  1. 弄清楚什么是前序遍历

  2. 画出树并用正确的数字标记每个节点，以便预购会返回他们需要的东西。

  3. 完成您需要做的事情，更容易使用 3 节点树并扩大规模。

例如

   1
  / \ 
 2   3

这就是你需要的

所以你可以看到粗略的想法是

Given X

  Set node.value = X
  X = Call on Left with X + 1    # add null check
  X = Call on Right with X + 1   # add null check
  return X

并且您的 numberMethod() 将是一个包装器，在检查空根之后，它会在 X =1 的根节点上调用上述函数。

于 2013-08-22T02:57:31.433 回答
0

因为我没有很好地开始使用java。对于任何寻找 CPP 实现的人，我已经尝试过并且它在许多测试用例中都有效。

这是我的 CPP 实施

struct Node{
      int data;
      Node* left, *right;
}
    
int NumberNodes(Node *root){
       
      if(root == NULL)
              return 0;
      
      if(root -> left != NULL)
              root -> left -> data = root -> data + 1;
      int l = NumberNodes(root -> left);

      if(root -> right != NULL)
              root -> right -> data = max(root->data, l) + 1;
      int r = NumberNodes(root -> right);

      return max(l, max(r, root->data));
}

int main(){
      Node *root = new Node();    //Or provide the root of your    ///  binary tree as mentioned in problem. 
      root->data = 1;
      int count = NumberNodes(root);  // count has the number of nodes in tree. 
}
于 2020-10-10T08:24:32.443 回答