如何用递归搜索二叉树并判断是否包含指定字符串？

看起来你已经搭好了二叉树的基本结构，不过代码好像没写完（最后那个构造函数的Strin应该是笔误成String了吧？），我来帮你补上判断逻辑，顺便梳理下递归的思路~

首先先把你提供的代码整理好，修正笔误后的版本：

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

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

    public BinaryTree(String d) { 
        data = d; 
        leftChild = new BinaryTree(); 
        rightChild = new BinaryTree(); 
    } 

    // 推测你原本想写的带左右子节点的构造函数
    public BinaryTree(String d, BinaryTree left, BinaryTree right) {
        data = d;
        leftChild = left;
        rightChild = right;
    }
}

接下来咱们实现核心的递归判断方法，思路是深度优先遍历：

• 先判断当前节点是否为空（data为null），是空的话直接返回false
• 如果当前节点的data和目标字符串匹配，直接返回true
• 递归检查左子树，左子树找到匹配就返回true
• 最后递归检查右子树，返回右子树的检查结果

把这个方法加到BinaryTree类里就行：

// 判断树中是否包含指定字符串的递归方法
public boolean contains(String target) {
    // 空节点直接返回false，避免空指针异常
    if (data == null) {
        return false;
    }
    // 当前节点匹配目标字符串，返回true
    if (data.equals(target)) {
        return true;
    }
    // 先递归查左子树，找到就直接返回
    if (leftChild.contains(target)) {
        return true;
    }
    // 左子树没找到，查右子树并返回结果
    return rightChild.contains(target);
}

额外补充： #

• 如果需要忽略大小写匹配，可以把data.equals(target)改成data.equalsIgnoreCase(target)
• 你的无参构造函数会生成data为null的空节点，所以递归时一定要先判断data是否为null，不然会触发空指针异常
• 这个方法会在找到第一个匹配的节点就返回true，如果你的树允许重复字符串，也能满足需求

最后给你个简单的测试例子：

public static void main(String[] args) {
    // 构建一棵测试二叉树
    BinaryTree leftSubTree = new BinaryTree("apple");
    BinaryTree rightSubTree = new BinaryTree("banana");
    BinaryTree root = new BinaryTree("root", leftSubTree, rightSubTree);

    // 测试匹配情况
    System.out.println(root.contains("apple"));  // 输出 true
    System.out.println(root.contains("orange")); // 输出 false
}

内容的提问来源于stack exchange，提问作者user9245948