是否有解决二叉树问题的"策略"？

Question

我希望这是一个可以接受的问题.我理解递归的思维模式,我想要考虑基本情况然后是递归情况,但是考虑到一些比较困难的BST问题,我只是画空白而感觉就像我迷失了,没有一个好的方向.

以链接列表为例,似乎有一种模式可以解决问题,但BT似乎要么你知道也要不知道.任何提示/指针？我似乎已经解决的唯一概念是,如果我正在处理空节点并且我想对它们或它们做一些事情,我将把它作为一个案例

if(root == null)
     //do something

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

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

在考虑使用二叉树进行递归时,基本情况是一个空树,因此您可以在那里找到正确的轨道.另一个关键概念元素是根据根,左子树和右子树(其中任何一个可能为空)进行思考.

所以我会像这样打破你的样本问题:

• 如果树是空的,那就无所事事了
• 否则,将下一个数字分配给根(Aha! - 我需要将"下一个数字"传递给此方法.)
• 递归左子树,传递的数量超过当前数字.
• 递归正确的子树,传递...啊.我需要知道在处理左子树之后下一个数字是什么.因此,我需要调用左子树来返回下一个数字(比分配的最后一个数字多一个).这意味着我最好做同样的事情.这将是在右子树上递归后返回的数字.
• 当我在根节点上调用此方法时,它将在设置所有值后返回下一个可用的数字.设置的节点数量将比此少一个.
• 实际上,最好只返回最后使用的数字,而不是下一个可用数字.然后我不需要单独的函数只是从结果中减去一个.所以我最好修改之前的分析,并说要传递给方法的数字(以及返回的数字)应该是最后使用的数字(不是下一个可用的数字)并相应地调整所有处理.

有了它,你几乎有这个方法的大纲.这是我写它的方式:

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