java - BST - 计算具有左子节点和右子节点的节点

Question

如标题所述，我试图通过仅计算 BST 中同时具有左子节点和右子节点的节点来解决此问题。我正在努力思考解决这个问题的逻辑。

我想到了这样的事情。

首先，检查根是否为 null 或者它是否有任何 null 子级。接下来，向右遍历树并继续检查子节点，当满足条件时增加计数器。但是，当我到达结束节点并需要返回到有左子节点要遍历的节点时，会发生什么情况？我有一个临时节点来跟踪最近的父节点，但是当我需要上升不止一层时该怎么办？我假设这个问题的答案是递归解决它，但我什至不知道从哪里开始。

这是我所拥有的:

public int fullNodes() {
    int count = 0;
    Node n = root;
    Node temp = null;

    if (n == null || n.left == null && n.right == null) return count;

    count++; //increment count, since the root has children on both sides

    temp = n; //hold the previous place
    n = n.right; //go right

    //Now what?

    return count;
}

我在解决问题时仍然在努力递归思考，除了我的问题，你如何学会递归思考？只是大量的练习，还是有一些解决问题的技巧和技巧？

Answer 1

而不是使用临时变量来保存前一个节点(这仅适用于深度为 1 的情况)在子节点上调用相同的函数。

递归树遍历可能看起来像这样:

public int countSomething (Node node) {

    // Self;
    //   
    int result = 1;   // use your required logic here

    // Children;
    //    
    if (node.left != null)
        result += countSomething( node.left);
    if (node.right != null)
        result += countSomething( node.right);

    // done.
    return result;
}


// example usages
int treeTotal = countSomething( rootNode);
int subtreeTotal = countSomething( subtree);

然后，执行调用堆栈将保存函数的递归调用，每个调用都有其适当的上下文。当顶层调用返回时，它将对调用它的整个树/或子树的答案进行求和。

为 BST“节点同时具有左右子节点”添加适当的逻辑，而不是常量 1。