Java递归方法实现二叉树指定节点路径字符串构建

需要设计一个递归方法，用于在二叉树中查找存储指定字符的Node节点，找到后返回其路径地址：遍历过程中向左子节点走则添加字符"0"到字符串，向右子节点走则添加字符"1"。例如查找节点B返回"0"，查找节点H返回"110"。无需处理目标节点不存在或查找根节点的边缘情况。给定方法框架如下：

private String address(Node root, String building, char target){ 
   //building represents the String in progress that will eventually be returned when the correct Node is found.
   //target represents the target Node's character that we would look for in the Tree
   //root has left and right pointers to access children.
   //Node.getChar() can be used to access the Node's char and compare it to see if it matches target
}

递归核心采用深度优先遍历逻辑，每进入一个子节点就拼接对应方向的路径字符，找到目标节点时直接返回当前构建好的路径。具体实现步骤如下：

1. 匹配目标节点：如果当前节点的字符与目标字符一致，直接返回当前的building字符串（即已构建完成的路径）。
2. 递归左子树：若当前节点存在左子节点，将building拼接"0"后传入左子节点的递归调用，拿到结果后直接返回（题目保证目标存在，因此左子树遍历必然能找到或进入右子树）。
3. 递归右子树：同理，将building拼接"1"后传入右子节点的递归调用，返回最终结果。

完整实现代码：

private String address(Node root, String building, char target){ 
    // 找到目标节点，返回当前路径
    if (root.getChar() == target) {
        return building;
    }
    
    // 遍历左子树，路径追加"0"
    if (root.left != null) {
        String leftPath = address(root.left, building + "0", target);
        if (leftPath != null) {
            return leftPath;
        }
    }
    
    // 遍历右子树，路径追加"1"
    if (root.right != null) {
        String rightPath = address(root.right, building + "1", target);
        if (rightPath != null) {
            return rightPath;
        }
    }
    
    // 题目无需处理目标不存在场景，此处仅为语法完整性保留
    return null;
}

代码说明 #

• 每次递归调用都会基于当前路径拼接方向字符，传递给子节点，保证路径的连续性。
• 找到目标节点后立即返回路径，终止后续递归，避免无效遍历。
• 优先遍历左子树，符合常规深度优先遍历顺序，若目标在右子树，左子树遍历完成后会自动转向右子树递归。

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