二叉树递归Java实现：根节点到指定节点的路径字符串问题

Hey there! I see the issue with your current recursive code—let's break down what's going wrong and fix it step by step.

The Problem with Your Current Implementation #

Your code returns immediately after traversing the left subtree, even if it fails to find the target node p. For example, when searching for node 2:

1. Start at root 3, traverse left to 4 (path becomes "0").
2. At node 4, traverse left to 9 (path becomes "00").
3. Node 9 is a leaf and not the target, so it returns "-1".
4. Your code takes this "-1" and returns it right away, never checking node 4's right child (which is exactly the target node 2!).

The Fix: Check Left First, Fall Back to Right #

We need to adjust the logic to only return the left subtree result if it's a valid path (not "-1"). If the left subtree doesn't find the target, we then proceed to check the right subtree. Here's the corrected code:

public String traverse(TreeNode root, TreeNode p, String s) {
    // Base case: found the target node, return the built path
    if (root == p) {
        return s;
    }

    // First explore the left subtree
    if (root.left != null) {
        String leftResult = traverse(root.left, p, s + "0");
        // If left subtree found the target, return the path immediately
        if (!leftResult.equals("-1")) {
            return leftResult;
        }
    }

    // Left subtree didn't find it? Now explore the right subtree
    if (root.right != null) {
        String rightResult = traverse(root.right, p, s + "1");
        if (!rightResult.equals("-1")) {
            return rightResult;
        }
    }

    // Neither subtree found the target, return the "not found" marker
    return "-1";
}

How This Works for Your Example #

Let's walk through finding node 2 again with the fixed code:

1. Start at 3, move left to 4 (path becomes "0").
2. At 4, move left to 9 (path "00"). 9 isn't 2, returns "-1".
3. Back at node 4, since the left result is "-1", we now check the right subtree (node 2).
4. Traverse to node 2, which matches p—return the path "01", which propagates back up the recursion stack as the final result.

Optional Cleanliness Improvement #

Using "-1" as a "not found" marker works, but using null or Optional<String> is more idiomatic for Java (since "-1" could technically be a valid path in edge cases). If you're open to adjusting the return type, here's a cleaner version:

import java.util.Optional;

public Optional<String> traverse(TreeNode root, TreeNode p, String s) {
    if (root == p) {
        return Optional.of(s);
    }

    if (root.left != null) {
        Optional<String> leftResult = traverse(root.left, p, s + "0");
        if (leftResult.isPresent()) {
            return leftResult;
        }
    }

    if (root.right != null) {
        return traverse(root.right, p, s + "1");
    }

    return Optional.empty();
}

This avoids magic strings and makes the "not found" case explicit.

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