有没有解决二叉树问题的“策略”？

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，以确定是否有手段我前往左边的根或右边的根，因为它是一个二叉搜索树，但我仍然无法实现此功能... ahh编码块！

Answer 1

一般 - 画出来，写你的Node类，并通过你需要做的

在这种情况下，有几个步骤是什么走，你将需要实质上反向工程了。

1. 弄清楚什么是序遍历

2. 绘制出树和标签正确数量的每个节点，以便序将返回他们需要什么。

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

E.摹

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的根节点。

Answer 2

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

所以我会打破你的样品问题下来是这样的：

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

因此，你几乎已经有了该方法的概要。以下是我如何写它：

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

Answer 3

首先，没有空节点。可以为空的是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 ; 
} 

计数与节点的值无关。这只与他们的立场有关。正确或者左边都是重要的。