\n \ucef4\ud4e8\ud130 \uacfc\ud559\uc5d0\uc11c \ud2b8\ub9ac\ub294 \uacc4\uce35\uc801 \ub370\uc774\ud130 \uad6c\uc870\uc758 \ud55c \uc885\ub958\ub85c, \ub178\ub4dc\ub85c \uc774\ub8e8\uc5b4\uc9c4 \uadf8\ub798\ud504\uc758 \uc77c\uc885\uc785\ub2c8\ub2e4. \ubcf8 \uac15\uc88c\uc5d0\uc11c\ub294 \uc2a4\uc704\ud504\ud2b8\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc8fc\uc5b4\uc9c4 \ub178\ub4dc\uc758 \ubd80\ubaa8 \ub178\ub4dc\ub97c \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\n \uc8fc\uc5b4\uc9c4 \uc774\uc9c4 \ud2b8\ub9ac\uc5d0\uc11c \ud2b9\uc815 \ub178\ub4dc\uc758 \ubd80\ubaa8 \ub178\ub4dc\ub97c \ucc3e\ub294 \ud568\uc218\ub97c \uc791\uc131\ud558\uc2dc\uc624. \ud2b8\ub9ac\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ubc29\uc2dd\uc73c\ub85c \ud45c\ud604\ub429\ub2c8\ub2e4.\n<\/p>\n
\nclass TreeNode {\n var value: Int\n var left: TreeNode?\n var right: TreeNode?\n \n init(value: Int) {\n self.value = value\n }\n}\n<\/code><\/pre>\n\uc704\uc640 \uac19\uc740 \uad6c\uc870\uccb4\uac00 \uc8fc\uc5b4\uc9c8 \uac83\uc785\ub2c8\ub2e4. \uc774 \uad6c\uc870\uccb4\ub97c \uc0ac\uc6a9\ud558\ub294 \uc774\uc9c4 \ud2b8\ub9ac\uc5d0\uc11c \ud2b9\uc815 \ub178\ub4dc\uc758 \ubd80\ubaa8 \ub178\ub4dc\ub97c \ucc3e\ub294 `findParent` \ud568\uc218\ub97c \uad6c\ud604\ud569\ub2c8\ub2e4.<\/p>\n
\ud568\uc218 \uc2dc\uadf8\ub2c8\ucc98<\/h3>\n\nfunc findParent(root: TreeNode?, target: Int) -> Int?\n<\/code><\/pre>\n\uc785\ub825<\/h2>\n\n- root<\/strong>: \uc774\uc9c4 \ud2b8\ub9ac\uc758 \ub8e8\ud2b8 \ub178\ub4dc (TreeNode? \ud0c0\uc785)<\/li>\n
- target<\/strong>: \ubd80\ubaa8\ub97c \ucc3e\uace0\uc790 \ud558\ub294 \ub178\ub4dc\uc758 \uac12 (Int \ud0c0\uc785)<\/li>\n<\/ul>\n
\ucd9c\ub825<\/h2>\n
\n \uc8fc\uc5b4\uc9c4 \ub178\ub4dc\uc758 \ubd80\ubaa8 \ub178\ub4dc\uc758 \uac12. \ub9cc\uc57d \uc8fc\uc5b4\uc9c4 \ub178\ub4dc\uac00 \uc874\uc7ac\ud558\uc9c0 \uc54a\uac70\ub098 \ub8e8\ud2b8 \ub178\ub4dc\uac00 \ub300\uc0c1\uc778 \uacbd\uc6b0\uc5d0\ub294 nil<\/code>\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4.\n<\/p>\n\uc608\uc81c<\/h2>\n\n\ub9cc\uc57d \ub2e4\uc74c\uacfc \uac19\uc740 \uc774\uc9c4 \ud2b8\ub9ac\uac00 \uc788\ub2e4\uace0 \uac00\uc815\ud569\ub2c8\ub2e4:\n\n 1\n \/ \\\n 2 3\n \/ \\ \/ \\\n 4 5 6 7\n\n findParent(root: rootNode, target: 5) \u2794 2\n findParent(root: rootNode, target: 1) \u2794 nil\n findParent(root: rootNode, target: 8) \u2794 nil\n <\/code><\/pre>\n<\/div>\n\uc54c\uace0\ub9ac\uc998 \uc124\uacc4<\/h2>\n
\n \ubd80\ubaa8 \ub178\ub4dc\ub97c \ucc3e\uae30 \uc704\ud574\uc11c\ub294 \uc774\uc9c4 \ud2b8\ub9ac\ub97c \ud0d0\uc0c9\ud574\uc57c \ud569\ub2c8\ub2e4. \uc77c\ubc18\uc801\uc778 \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc778 \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS) \ub610\ub294 \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9(BFS)\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc5ec\uae30\uc11c\ub294 DFS\ub97c \uc774\uc6a9\ud558\uc5ec \uc7ac\uadc0\uc801\uc73c\ub85c \ud2b8\ub9ac\ub97c \ud0d0\uc0c9\ud558\ub294 \ubc29\ubc95\uc744 \ucc44\ud0dd\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n
DFS \ud0d0\uc0c9 \ubc29\ubc95<\/h3>\n\n- \ud604\uc7ac \ub178\ub4dc\uac00
nil<\/code>\uc778 \uacbd\uc6b0 \ud0d0\uc0c9 \uc885\ub8cc<\/li>\n- \ud604\uc7ac \ub178\ub4dc\uc758 \uac12\uc774
target<\/code>\uacfc \uc77c\uce58\ud558\ub294\uc9c0 \ud655\uc778<\/li>\n- \uc77c\uce58\ud558\uba74 \ud604\uc7ac \ub178\ub4dc\uc758 \ubd80\ubaa8 \uac12\uc744 \ubc18\ud658<\/li>\n
- \uc77c\uce58\ud558\uc9c0 \uc54a\uc73c\uba74 \uc67c\ucabd \ubc0f \uc624\ub978\ucabd \uc790\uc2dd \ub178\ub4dc\ub85c \uc7ac\uadc0 \ud638\ucd9c<\/li>\n<\/ul>\n
\uad6c\ud604<\/h2>\n
\uc774\uc81c \uc704\uc758 \uc54c\uace0\ub9ac\uc998\uc744 \ubc14\ud0d5\uc73c\ub85c \ud568\uc218 findParent<\/code>\ub97c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n\nfunc findParent(root: TreeNode?, target: Int) -> Int? {\n return findParentHelper(root, target: target, parent: nil)\n}\n\nprivate func findParentHelper(_ node: TreeNode?, target: Int, parent: TreeNode?) -> Int? {\n guard let node = node else { return nil } \/\/ \ud604\uc7ac \ub178\ub4dc\uac00 nil\uc778 \uacbd\uc6b0\n\n if node.value == target {\n return parent?.value \/\/ \ubd80\ubaa8 \ub178\ub4dc\ub97c \ubc18\ud658\n }\n\n \/\/ \uc67c\ucabd \uc790\uc2dd \ud0d0\uc0c9\n let leftResult = findParentHelper(node.left, target: target, parent: node)\n if leftResult != nil {\n return leftResult \/\/ \uc67c\ucabd\uc5d0\uc11c \ubd80\ubaa8\ub97c \ucc3e\uc558\ub2e4\uba74 \ubc18\ud658\n }\n\n \/\/ \uc624\ub978\ucabd \uc790\uc2dd \ud0d0\uc0c9\n return findParentHelper(node.right, target: target, parent: node)\n}\n<\/code><\/pre>\n\ud14c\uc2a4\ud2b8<\/h2>\n
\uc774\uc81c \uad6c\ud604\ud55c \ud568\uc218\ub97c \ud14c\uc2a4\ud2b8\ud558\uc5ec \uc62c\ubc14\ub974\uac8c \uc791\ub3d9\ud558\ub294\uc9c0 \ud655\uc778\ud558\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\nlet rootNode = TreeNode(value: 1)\nrootNode.left = TreeNode(value: 2)\nrootNode.right = TreeNode(value: 3)\nrootNode.left?.left = TreeNode(value: 4)\nrootNode.left?.right = TreeNode(value: 5)\nrootNode.right?.left = TreeNode(value: 6)\nrootNode.right?.right = TreeNode(value: 7)\n\nprint(findParent(root: rootNode, target: 5) ?? \"nil\") \/\/ 2\nprint(findParent(root: rootNode, target: 1) ?? \"nil\") \/\/ nil\nprint(findParent(root: rootNode, target: 8) ?? \"nil\") \/\/ nil\n<\/code><\/pre>\n\uacb0\ub860<\/h2>\n
\n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc2a4\uc704\ud504\ud2b8\ub85c \uc774\uc9c4 \ud2b8\ub9ac\uc5d0\uc11c \ud2b9\uc815 \ub178\ub4dc\uc758 \ubd80\ubaa8\ub97c \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud574\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \ud2b8\ub9ac \uad6c\uc870\uc758 \ud0d0\uc0c9 \ubb38\uc81c\uc5d0\uc11c DFS\uc758 \uae30\ubcf8 \uac1c\ub150\uc744 \uc801\uc6a9\ud558\uc5ec \ucf54\ub4dc\ub97c \uc791\uc131\ud558\ub294 \ubc29\ubc95\uc744 \ubc30\ucce4\uc2b5\ub2c8\ub2e4.
\n \uc774\ub7ec\ud55c \ubb38\uc81c\ub97c \ud1b5\ud574 \ud2b8\ub9ac\uc5d0 \ub300\ud55c \uc774\ud574\uc640 \uc7ac\uadc0\uc801\uc778 \uc0ac\uace0\ub97c \ud0a4\uc6b8 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\ucd94\uac00\uc801\uc73c\ub85c \ud2b8\ub9ac\uc758 \ub2e4\ub978 \uc18d\uc131\uc5d0 \ub300\ud55c \ubb38\uc81c\ub3c4 \ud480\uc5b4\ubcf4\uba70 \uc2e4\ub825\uc744 \uc313\uae38 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"