递归查找树中节点父节点的代码问题及修复咨询

Let's break down the issues with your current implementation and fix them step by step:

Key Problems in Your Code #

• Non-optional parentNode parameter: Your method defines parentNode: Node as a non-optional type, which means you can't pass nil when calling it on the root node (this should be causing a compile error right away).
• Incorrect parent node return logic: When a child node finds the target, you're returning the parentNode passed into the current method instead of the current node (self) — which is actually the direct parent of the found child.

Fixed Implementation #

Here's the corrected extension that addresses both issues, plus some readability improvements:

class Node {
    var id: String
    var children: [Node] = []
    
    init(id: String) {
        self.id = id
    }
}

extension Node {
    func searchNodeAndParent(_ targetId: String, parentNode: Node?) -> (node: Node?, parent: Node?) {
        // Check if current node matches the target ID
        if self.id == targetId {
            return (self, parentNode)
        }
        
        // Recursively check each child node
        for child in children {
            let (foundNode, foundParent) = child.searchNodeAndParent(targetId, parentNode: self)
            if foundNode != nil {
                return (foundNode, foundParent)
            }
        }
        
        // Target not found in this branch of the tree
        return (nil, nil)
    }
}

What Changed? #

1. Optional parentNode parameter: We updated parentNode: Node to parentNode: Node? so you can pass nil when starting the search from the root (since the root has no parent).
2. Corrected parent return logic: When recursing into a child, we pass self as its parent. If the child finds the target, we return the found node along with the parent that was passed to the child (which is self — the actual direct parent of the found node).
3. Readability tweaks: Renamed the search parameter to targetId for clarity, and added labeled return values (node: and parent:) to make working with the result more intuitive.

How to Use It #

// Example tree setup
let root = Node(id: "root")
let child1 = Node(id: "child1")
let child2 = Node(id: "child2")
root.children = [child1, child2]
let grandchild = Node(id: "grandchild")
child1.children = [grandchild]

// Search for the grandchild node
let (foundNode, parentNode) = root.searchNodeAndParent("grandchild", parentNode: nil)
print(foundNode?.id) // Prints "grandchild"
print(parentNode?.id) // Prints "child1"

// Search for the root node
let (rootNode, rootParent) = root.searchNodeAndParent("root", parentNode: nil)
print(rootNode?.id) // Prints "root"
print(rootParent) // Prints nil (correct, since root has no parent)

Edge Cases Handled #

• Target is the root node (returns the root with nil parent)
• Target is a deep descendant (returns the node and its immediate parent)
• Target doesn't exist in the tree (returns (nil, nil))

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