\uc548\ub155\ud558\uc138\uc694, \uc5ec\ub7ec\ubd84! \uc624\ub298\uc740 \ud30c\uc774\uc36c\uc744 \uc774\uc6a9\ud55c \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ub4f1\uc7a5\ud558\ub294 \ubb38\uc81c \uc911 \ud558\ub098\uc778 “\ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1 \uad6c\ud558\uae30”\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \uc758\ubbf8\ud558\ub294 ‘Lowest Common Ancestor (LCA)’\ub97c \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \uc0c1\uc138\ud788 \uc124\uba85\ud558\uba70, \uad00\ub828\ub41c \uc608\uc81c \ubb38\uc81c \ubc0f \uadf8 \ud574\uacb0 \uacfc\uc815\uc744 \ud568\uaed8 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
1. \ubb38\uc81c \uc815\uc758<\/h2>\n
\uc8fc\uc5b4\uc9c4 \uc774\uc9c4\ud2b8\ub9ac\uc5d0\uc11c \ub450 \ub178\ub4dc A\uc640 B\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc774\ub780 \ub450 \ub178\ub4dc\ub97c \ub3d9\uc2dc\uc5d0 \ubd80\ubaa8\ub85c \uac00\uc9c0\ub294 \uac00\uc7a5 \uae4a\uc740 \ub178\ub4dc\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \ub2e4\uc74c\uacfc \uac19\uc740 \uc774\uc9c4\ud2b8\ub9ac\uac00 \uc788\ub2e4\uace0 \uac00\uc815\ud574\ubd05\uc2dc\ub2e4.<\/p>\n
\n 3\n \/ \\\n 5 1\n \/ \\ \/ \\\n 6 2 0 8\n \/ \\\n 7 4\n <\/pre>\n\uc704 \ud2b8\ub9ac\uc5d0\uc11c \ub178\ub4dc 5\uc640 \ub178\ub4dc 1\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc740 \ub178\ub4dc 3\uc785\ub2c8\ub2e4. \uadf8\ub7ec\ub098 \ub178\ub4dc 5\uc640 \ub178\ub4dc 4\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc740 \ub178\ub4dc 5\uc785\ub2c8\ub2e4.<\/p>\n
2. \ubb38\uc81c \uc694\uad6c \uc0ac\ud56d<\/h2>\n
\n
- \uc785\ub825: \uc774\uc9c4\ud2b8\ub9ac\uc758 \ub8e8\ud2b8 \ub178\ub4dc\uc640 \ub450 \ub178\ub4dc A, B<\/li>\n
- \ucd9c\ub825: A\uc640 B\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1 \ub178\ub4dc\ub97c \ubc18\ud658<\/li>\n<\/ul>\n
3. \uc54c\uace0\ub9ac\uc998 \uc811\uadfc\ubc95<\/h2>\n
\ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\uae30 \uc704\ud55c \uc5ec\ub7ec \uc811\uadfc\ubc95\uc774 \uc788\uc9c0\ub9cc, \uac00\uc7a5 \uac04\ub2e8\ud55c \ubc29\ubc95\uc740 DFS(\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9)\ub97c \uc774\uc6a9\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. DFS \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uba74 \uac01 \ub178\ub4dc\ub97c \ubc29\ubb38\ud558\uba74\uc11c A\uc640 B\ub97c \ucc3e\uace0, \ub450 \ub178\ub4dc\uc758 \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucd94\uc801\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
3.1 DFS \ud0d0\uc0c9 \ubc29\ubc95<\/h3>\n
DFS\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc774\uc9c4\ud2b8\ub9ac\ub97c \ud0d0\uc0c9\ud558\uba74\uc11c \ud604\uc7ac \ub178\ub4dc\uac00 \ub450 \ub178\ub4dc A\uc640 B \uc911 \ud558\ub098\uc640 \uc77c\uce58\ud558\ub294\uc9c0 \ud655\uc778\ud569\ub2c8\ub2e4. \uc77c\uce58\ud558\ub294 \uacbd\uc6b0 \ud574\ub2f9 \ub178\ub4dc\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4. \uadf8\ub807\uc9c0 \uc54a\ub2e4\uba74 \ub450 \uac1c\uc758 \uc11c\ube0c\ud2b8\ub9ac\uc5d0\uc11c \uac01\uac01 A\uc640 B\ub97c \ucc3e\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c \ub2e8\uacc4\ub85c \uc774 \ub450 \uc11c\ube0c\ud2b8\ub9ac\uc758 \uacb0\uacfc\ub97c \uacb0\ud569\ud558\uc5ec \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\uc2b5\ub2c8\ub2e4.<\/p>\n
3.2 \uad6c\ud604<\/h3>\n
\uc774\uc81c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \ucf54\ub4dc\ub97c \uc791\uc131\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\nclass TreeNode:\n def __init__(self, value):\n self.value = value\n self.left = None\n self.right = None\n\ndef lowest_common_ancestor(root, node1, node2):\n if root is None:\n return None\n\n # base case: if the current root is one of the nodes\n if root == node1 or root == node2:\n return root\n\n # look for node1 and node2 in the left and right subtrees\n left_lca = lowest_common_ancestor(root.left, node1, node2)\n right_lca = lowest_common_ancestor(root.right, node1, node2)\n\n # If both left_lca and right_lca are not None, it means\n # one node is present in one subtree and the other is present in the other subtree\n if left_lca and right_lca:\n return root\n\n # Otherwise return the non-null value\n return left_lca if left_lca is not None else right_lca\n <\/code><\/pre>\n4. \ucf54\ub4dc \uc124\uba85<\/h2>\n
\uba3c\uc800, \uc774\uc9c4 \ud2b8\ub9ac\uc758 \uac01 \ub178\ub4dc\ub97c \ub098\ud0c0\ub0b4\ub294
TreeNode<\/code> \ud074\ub798\uc2a4\ub97c \uc815\uc758\ud569\ub2c8\ub2e4. \uc774 \ud074\ub798\uc2a4\ub294 \uac01 \ub178\ub4dc\uc758 \uac12\uacfc \uc67c\ucabd, \uc624\ub978\ucabd \uc790\uc2dd \ub178\ub4dc\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4. \ub2e4\uc74c\uc73c\ub85c,lowest_common_ancestor<\/code> \ud568\uc218\ub97c \uc815\uc758\ud558\uc5ec \uc8fc\uc5b4\uc9c4 \ub8e8\ud2b8 \ub178\ub4dc\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \ub450 \uac1c\uc758 \ub178\ub4dc\uc778node1<\/code>\uacfcnode2<\/code>\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\uc2b5\ub2c8\ub2e4.<\/p>\n4.1 \uae30\ubcf8 \uc870\uac74<\/h3>\n
\ub8e8\ud2b8 \ub178\ub4dc\uac00
None<\/code>\uc778 \uacbd\uc6b0\uc5d0\ub294None<\/code>\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4. \ud604\uc7ac \ub8e8\ud2b8\uac00node1<\/code> \ub610\ub294node2<\/code>\uc640 \ub3d9\uc77c\ud55c \uacbd\uc6b0\uc5d0\ub294 \ud574\ub2f9 \ub178\ub4dc\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4.<\/p>\n4.2 \uc7ac\uadc0\uc801 \ud0d0\uc0c9<\/h3>\n
\uadf8 \ud6c4, \uc67c\ucabd \uc11c\ube0c\ud2b8\ub9ac\uc640 \uc624\ub978\ucabd \uc11c\ube0c\ud2b8\ub9ac \uac01\uac01\uc5d0\uc11c \uc7ac\uadc0\uc801\uc73c\ub85c LCA\ub97c \ucc3e\uc2b5\ub2c8\ub2e4. \ub450 \uc11c\ube0c\ud2b8\ub9ac\uc5d0\uc11c \ubaa8\ub450 \ubc1c\uacac\ub41c \ub178\ub4dc\uac00 \uc788\uc744 \uacbd\uc6b0 \ud604\uc7ac \ub178\ub4dc\uac00 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc785\ub2c8\ub2e4. \uadf8\ub807\uc9c0 \uc54a\uc73c\uba74 \ubc1c\uacac\ub41c \ub178\ub4dc\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4.<\/p>\n
5. \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4<\/h2>\n
\ud568\uc218\ub97c \ud14c\uc2a4\ud2b8\ud558\uae30 \uc704\ud574 \ub2e4\uc74c\uc758 \ud2b8\ub9ac\ub97c \uad6c\uc131\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\n root = TreeNode(3)\n root.left = TreeNode(5)\n root.right = TreeNode(1)\n root.left.left = TreeNode(6)\n root.left.right = TreeNode(2)\n root.right.left = TreeNode(0)\n root.right.right = TreeNode(8)\n root.left.right.left = TreeNode(7)\n root.left.right.right = TreeNode(4)\n <\/pre>\n\n# Test case 1: Finding LCA of 5 and 1\nlca = lowest_common_ancestor(root, root.left, root.right) # should return TreeNode(3)\n\n# Test case 2: Finding LCA of 5 and 4\nlca = lowest_common_ancestor(root, root.left, root.left.right.right) # should return TreeNode(5)\n <\/code><\/pre>\n6. \uacb0\ub860<\/h2>\n
\uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \ud30c\uc774\uc36c\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc774\uc9c4 \ud2b8\ub9ac\uc5d0\uc11c \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\ub294 \ubc29\ubc95\uc744 \uc54c\uc544\ubcf4\uc558\uc2b5\ub2c8\ub2e4. DFS \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc0b4\ud3b4\ubcf4\uc558\uc73c\uba70, \uc774\ub97c \ud1b5\ud574 \uc774\uc9c4 \ud2b8\ub9ac\uc5d0 \ub300\ud55c \uc774\ud574\ub97c \ub192\uc77c \uc218 \uc788\uc5c8\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c \uac15\uc88c\uc5d0\uc11c\ub294 \ubcf4\ub2e4 \ubcf5\uc7a1\ud55c \uc774\uc9c4 \ud2b8\ub9ac \ubb38\uc81c\ub97c \ub2e4\ub8f0 \uc608\uc815\uc774\ub2c8, \ub9ce\uc740 \uad00\uc2ec \ubd80\ud0c1\ub4dc\ub9bd\ub2c8\ub2e4!<\/p>\n
\uc774 \uae00\uc744 \ud1b5\ud574 \uc5ec\ub7ec\ubd84\uaed8\uc11c LCA \ubb38\uc81c\ub97c \uc774\ud574\ud558\uace0, \uc774\ub97c \ud574\uacb0\ud560 \uc218 \uc788\ub294 \ub2a5\ub825\uc744 \ud0a4\uc6b0\uc168\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4!<\/p>\n<\/article>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"