通用树结构递归查找目标节点父节点的实现疑问

问题描述 #

给定通用树的根节点和待搜索的token（节点值），实现一个函数接收根节点与搜索key，返回找到目标节点的父节点。提供的Node类定义如下：

import java.util.ArrayList;
public class Node {
    int key;
     ArrayList<Node> children = new ArrayList<Node>();
    public  boolean hasChildren(){
        if(children.size() !=0){
            return true;
        }
        else {
            return false;
        }
    }
}

尝试用层序遍历实现时，不清楚如何编写判断条件返回父节点，也不知道如何正确将子节点加入队列，未完成的代码如下：

static Node findParent(Node root,int token){
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()){
        Node temp = queue.poll();
        if(temp.hasChildren()){
            for(int i=0;i<temp.children.size()){
                if()
            }
        }
    }
}

修正后的层序遍历实现 #

层序遍历的核心逻辑是：遍历每个节点的子节点，若子节点匹配目标token，当前节点即为父节点；若不匹配，则将子节点加入队列继续遍历。以下是完整可运行的代码：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Node {
    int key;
    ArrayList<Node> children = new ArrayList<Node>();
    
    public boolean hasChildren(){
        return children.size() != 0;
    }
    
    static Node findParent(Node root, int token){
        // 边界处理：根节点是目标时，无父节点
        if(root.key == token){
            return null;
        }
        
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        
        while(!queue.isEmpty()){
            Node currentNode = queue.poll();
            
            // 遍历当前节点的所有子节点
            for(Node child : currentNode.children){
                // 找到目标节点，返回当前父节点
                if(child.key == token){
                    return currentNode;
                }
                // 未找到，将子节点加入队列继续下一层遍历
                queue.add(child);
            }
        }
        
        // 树中无目标节点，返回null
        return null;
    }
}

关键说明 #

• 边界处理：先判断根节点是否为目标，直接返回null（根节点没有父节点）
• 遍历逻辑优化：使用增强for循环遍历子节点，无需调用hasChildren()——空列表时循环不会执行，更简洁高效
• 条件判断：遍历子节点时直接检查是否匹配token，匹配立即返回当前节点，无需继续遍历
• 队列操作：未匹配的子节点加入队列，保证层序遍历的顺序，覆盖树的所有节点

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