java - 是否有任何 "strategies"来解决二叉树问题？

Question

我希望这是一个可以接受的问题。我理解递归的思维模式，我想考虑基本情况，然后是递归情况，但是对于一些更困难的 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作为一种确定我是到左根还是右根的方法，因为它是一个二叉搜索树，但我仍然无法实现这个功能......啊编码块!

Answer 1

在考虑使用二叉树进行递归时，基本情况是一棵空树，因此您在正确的轨道上。另一个关键的概念元素是根据根、左子树和右子树(其中一个可能为空)来考虑。

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

如果树是空的，则无事可做

否则，将下一个数字分配给根(啊哈! - 我需要将“下一个数字”传递给此方法。)

在左子树上递归，传递比当前数字多一个。

在右子树上递归，传递 . . .啊。我需要知道处理左子树后的下一个数字是什么。因此，我需要调用左子树来返回下一个数字(比分配的最后一个数字多一个)。这意味着我最好做同样的事情。这将是在右子树上递归后返回的数字。

当我在根节点上调用此方法时，它将在设置所有值后返回下一个可用数字。设置的节点数将比这少一个。

实际上，最好只返回最后使用的数字，而不是下一个可用的数字。然后我不需要一个单独的函数来从结果中减去一个。所以我最好修改一下之前的分析，并说要传递给方法的数字(以及返回的数字)应该是最后使用的数字(而不是下一个可用数字)，并相应地调整所有处理。

有了这个，你几乎有了这个方法的大纲。这是我将如何编写它:

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