java - 创建给定 BinaryTree 的递归方法

Question

我正在学习几个小时后的考试，我正在复习一些练习题，但我在递归相关问题上确实遇到了麻烦。我想知道是否有人可以引导我完成这些操作？

使用下面的BinaryTree 类，创建以下递归方法:

• sum() – 返回二叉树中所有值的总和。
• countGreaterThan(int) – 返回值大于指定整数的节点数。
• isValidSearchTree() – 如果二叉树是有效的搜索树，则返回 true，否则返回 false。

我了解了如何创建这些函数的基本前提，例如，对于 sum 函数，它通常会类似于:

int sum = 0
for(int i; i<binaryTree.size(); i++){
    sum += binaryTree[i]
}

或者类似的东西。但我真的不知道如何将这些概念应用于具有节点的二叉树并使它们也递归？下面给出了我提供的代码。

public class BinaryTree {
 private int data;
 private BinaryTree leftChild;
 private BinaryTree rightChild;

 public BinaryTree(int val) {
     data = val;
     leftChild = null;
     rightChild = null;
  }

  // Get methods
 public int getData() { return data; }
 public BinaryTree getLeftChild() { return leftChild; }
 public BinaryTree getRightChild() { return rightChild; }

 // Set methods
 public void setData(int val) { data = val; }
 public void setLeftChild(BinaryTree left) { leftChild = left; }
 public void setRightChild(BinaryTree right) { rightChild = right; }
}

Answer 1

你应该研究recursion的力量 ，但我已经编写了您要求的方法，所有这些都像魅力一样工作:

/*
* INPUT:   Root node
* OUTPUT:  Sum of the data of all nodes of tree
*/

public void sum(TreeNode node)
{
    if(node == null)
        return;

    sum(node.leftNode);  // recursive call to left subtree of each node
    sum += node.data;
    sum(node.rightNode);  // recursive call to right subtree of each node
}


/*
* INPUT:   Root node , threshold value
* OUTPUT:  sum of all node's data, that rae greater than "value"
*/

public void countGreaterThan(TreeNode node, int value)
{
    if(node == null)
        return;

    countGreaterThan(node.leftNode,value);
    if( node.data > value)    // only adds is node.data is greater than given value 
        sum += node.data;
    countGreaterThan(node.rightNode,value);
}   

/*
* INPUT:  nothing
* OUTPUT:  call to its helper function, taking MIN, MAX, and root as input
*/

public boolean isBST()  
{ 
    return isBSThelper(root, Integer.MIN_VALUE,  Integer.MAX_VALUE); 
}   

public boolean isBSThelper(TreeNode node, int min, int max) 
{ 
    if (node == null)   //empty tree is always a BST 
        return true; 

    if (node.data < min || node.data > max) //if node breaks the min/max condition 
        return false; 

    // recursive call to left subtree and right subtree
    return (isBSThelper(node.leftNode, min, node.data-1) && isBSThelper(node.rightNode, node.data+1, max)); 
}