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设置适当的逻辑"nodehavebotleft&rightchildren"，而不是常量1。

Answer 2

首先让我们创建节点类的表示

class Node {
public Node left;
public Node right;
public Node(){}
public Node(Node left, Node right) {
this.left = left;
this.right = right;
}
}

然后我们编写我们的检索函数和使用您的函数的客户端

public class Main {   
public static int countNodes(Node root) {
if(root!=null && root.left!=null && root.right!=null) {
return 1+countNodes(root.left)+countNodes(root.right);
}
return 0;
}
public static void main(String[] args) {
Node right = new Node();
Node left = new Node();
Node root = new Node(left, right);
root.right = new Node(new Node(), new Node());
System.out.println(countNodes(root));
}
}