如何在递归遍历二叉树并检查具有匹配值的特定节点时 return 布尔值？

Question

我目前正在 Java 研究树数据结构和递归。我的计划是有一个递归方法，它遍历树并检查树中的任何节点是否具有该特定值。如果是，方法 returns true，否则方法 returns false。为了更好地理解，我添加了打印语句。我遇到的问题是，即使节点存在该特定值，该方法也会返回 false。只有 return 为真，如果该值与根值匹配。我的方法如下所示：

//Calling this method in the main function
    public boolean checkForValue(int value) {
        return checkForValue(value, root);
    }
    
    private boolean checkForValue(int value, TreeNode current) {
        //Checking if the current value is null, if so return false
        if(current == null) {
            return false;
        } else {
            //if the current nodes value matches the value we are looking for
            // it should return true
            if(current.value == value) {
                
                System.out.println("Found a Node with same value");
                
                return true;
            }
            //if it wasnt the value, call the method recusrivly
            //with the current.right node
             else {
                System.out.println("Value didnt matched the current Node");
                checkForValue(value, current.right);
                checkForValue(value, current.left);
                return false;
                
            }
        }
        
    }

我的主要方法如下所示：

public static void main(String[] args) {
            Tree tree = new Tree();
            tree.add(new TreeNode(20));
            tree.add(new TreeNode(30));
            tree.add(new TreeNode(10));
            tree.add(new TreeNode(15));
            tree.add(new TreeNode(5));
            tree.add(new TreeNode(40));
            tree.add(new TreeNode(29));
            System.out.println(tree.checkForValue(40));
}

尽管树有一个值为 40 的节点，但它打印出 false。我的控制台在运行之后看起来像这样：

值与当前节点不匹配
值与当前节点不匹配
值与当前节点不匹配
值与当前节点不匹配
值与当前节点不匹配
找到一个具有相同值的节点
值与当前节点不匹配

找到节点（第 6 行）后，它应该 return 为真，不继续（第 7 行）。如果找到值，我如何确保停止？

Answer 1

您忽略了递归调用的结果。

而不是做：

checkForValue(value, current.right);  // Result ignored.
checkForValue(value, current.left);   // Result ignored.
return false;                         // Always returned.

改为：

return checkForValue(value, current.right)
    || checkForValue(value, current.left);

如果右分支结果为假，这只会下降到左分支。

如何在递归遍历二叉树并检查具有匹配值的特定节点时 return 布尔值？

How can I return a boolean while traversing a BinaryTree recursivly and checking for a specific Node with matching Value?

java

binary-tree

recursive-datastructures