\uc791\uc131\uc790: \uc870\uad11\ud615<\/p>\n
\uc791\uc131\uc77c: [\uc624\ub298\uc758 \ub0a0\uc9dc]<\/p>\n<\/header>\n \n \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ud480\uc774\uc5d0\uc11c\ub294 \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub2a5\ub825\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \uadf8 \uc911\uc5d0\uc11c\ub3c4 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1(Lowest Common Ancestor, LCA) \ubb38\uc81c\ub294 \ud2b8\ub9ac \uad6c\uc870\uc5d0\uc11c\uc758 \ub178\ub4dc \uac04\uc758 \uad00\uacc4\ub97c \uc774\ud574\ud558\ub294 \ub370 \ud544\uc218\uc801\uc778 \uac1c\ub150\uc785\ub2c8\ub2e4. \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 C#\uc744 \uc0ac\uc6a9\ud558\uc5ec \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \uad6c\ud558\ub294 \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n<\/section>\n \n \uc8fc\uc5b4\uc9c4 \uc774\uc9c4 \ud2b8\ub9ac\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \ub450 \ub178\ub4dc A\uc640 B\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1(LCA)\uc744 \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc774\uc9c4 \ud2b8\ub9ac\ub294 \uac01 \ub178\ub4dc\uac00 \ucd5c\ub300 \ub450 \uac1c\uc758 \uc790\uc2dd\uc744 \uac00\uc9c0\ub294 \uc790\ub8cc\uad6c\uc870\uc785\ub2c8\ub2e4. LCA\ub294 \ub450 \ub178\ub4dc A\uc640 B\uc758 \uac00\uc7a5 \uac00\uae4c\uc6b4 \uacf5\ud1b5 \uc870\uc0c1\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4.\n <\/p>\n \n \uc608\ub97c \ub4e4\uc5b4 \uc544\ub798\uc640 \uac19\uc740 \uc774\uc9c4 \ud2b8\ub9ac\uac00 \uc788\ub2e4\uace0 \uac00\uc815\ud574 \ubd05\uc2dc\ub2e4.\n <\/p>\n \n \uc774 \ud2b8\ub9ac\uc5d0\uc11c \ub178\ub4dc 4\uc640 5\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc740 2\uc785\ub2c8\ub2e4. \ub178\ub4dc 2\ub294 4\uc640 5\ub85c \uac00\ub294 \uacbd\ub85c\uc5d0\uc11c \uac00\uc7a5 \uac00\uae4c\uc6b4 \uc870\uc0c1\uc785\ub2c8\ub2e4.\n <\/p>\n<\/section>\n \n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub2e4\uc74c\uacfc \uac19\uc740 \uc811\uadfc \ubc29\uc2dd\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \uc9c0\uae08\ubd80\ud130 C#\uc73c\ub85c \uc774\uc9c4 \ud2b8\ub9ac\uc640 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\ub294 \ud568\uc218\ub97c \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uba3c\uc800 \ud2b8\ub9ac\ub97c \ub098\ud0c0\ub0b4\ub294 \ud074\ub798\uc2a4(TreeNode)\ub97c \uc815\uc758\ud558\uace0, \uadf8 \uc704\uc5d0 LCA\ub97c \ucc3e\ub294 \uba54\uc18c\ub4dc\ub97c \uc791\uc131\ud569\ub2c8\ub2e4.\n <\/p>\n \n \uc704 \ucf54\ub4dc\ub294 \uae30\ubcf8\uc801\uc778 \uc774\uc9c4 \ud2b8\ub9ac \ub178\ub4dc\ub97c \uc815\uc758\ud558\uace0, \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\ub294 \uba54\uc18c\ub4dc\ub97c \uad6c\ud604\ud55c \uc608\uc785\ub2c8\ub2e4.\n <\/p>\n<\/section>\n \n \uc774\uc81c \ucf54\ub4dc\ub97c \ud14c\uc2a4\ud2b8\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc544\ub798\uc640 \uac19\uc774 \uc774\uc9c4 \ud2b8\ub9ac\ub97c \uc0dd\uc131\ud558\uace0, LCA\ub97c \ucc3e\ub294 \ub85c\uc9c1\uc744 \uc2e4\ud589\ud574 \ubcfc \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \uc774 \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uba74 \ub178\ub4dc 4\uc640 5\uc758 LCA\ub294 2, \ub178\ub4dc 4\uc640 3\uc758 LCA\ub294 1\uc774 \ucd9c\ub825\ub429\ub2c8\ub2e4. \uc774\ub294 \uc6b0\ub9ac\uac00 \uc608\uce21\ud55c \uacb0\uacfc\uc640 \uc77c\uce58\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n \n \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 \uc774\uc9c4 \ud2b8\ub9ac\uc5d0\uc11c \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uc558\uc2b5\ub2c8\ub2e4. C#\uc73c\ub85c \uad6c\ud604\uc744 \ud1b5\ud574 \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \ubc30\uc591\ud560 \uc218 \uc788\uc5c8\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ud480\uc774\uc5d0\uc11c\uc758 \uae30\ubcf8 \uac1c\ub150\uc744 \ucda9\ubd84\ud788 \uc774\ud574\ud558\uace0 \ub2e4\uc591\ud55c \uc0c1\ud669\uc5d0 \uc801\uc6a9\ud574 \ubcf4\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4.\n <\/p>\n \n \uc55e\uc73c\ub85c\ub3c4 \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud1b5\ud574 \uc54c\uace0\ub9ac\uc998 \ub2a5\ub825\uc744 \ud5a5\uc0c1\uc2dc\ud0a4\uace0 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc88b\uc740 \uc131\uacfc\ub97c \ub0b4\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\ub4e4\uc5b4\uac00\uba70<\/h2>\n
\ubb38\uc81c \uc124\uba85<\/h2>\n
\n 1\n \/ \\\n 2 3\n \/ \\\n 4 5\n <\/pre>\n
\ubb38\uc81c \uc694\uad6c \uc0ac\ud56d<\/h2>\n
\n
\uc811\uadfc \ubc29\uc2dd<\/h2>\n
\n
\ucf54\ub4dc \uad6c\ud604<\/h2>\n
\nusing System;\nusing System.Collections.Generic;\n\npublic class TreeNode {\n public int Value;\n public TreeNode Left;\n public TreeNode Right;\n \n public TreeNode(int value) {\n Value = value;\n Left = Right = null;\n }\n}\n\npublic class BinaryTree {\n private TreeNode root;\n\n public BinaryTree(TreeNode root) {\n this.root = root;\n }\n\n public TreeNode FindLCA(int val1, int val2) {\n return FindLCA(root, val1, val2);\n }\n\n private TreeNode FindLCA(TreeNode node, int val1, int val2) {\n if (node == null) {\n return null;\n }\n if (node.Value == val1 || node.Value == val2) {\n return node;\n }\n\n TreeNode leftLCA = FindLCA(node.Left, val1, val2);\n TreeNode rightLCA = FindLCA(node.Right, val1, val2);\n\n if (leftLCA != null && rightLCA != null) {\n return node;\n }\n return (leftLCA != null) ? leftLCA : rightLCA;\n }\n}\n <\/pre>\n\ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4<\/h2>\n
\nclass Program {\n static void Main() {\n TreeNode root = new TreeNode(1);\n root.Left = new TreeNode(2);\n root.Right = new TreeNode(3);\n root.Left.Left = new TreeNode(4);\n root.Left.Right = new TreeNode(5);\n\n BinaryTree tree = new BinaryTree(root);\n\n TreeNode lca = tree.FindLCA(4, 5);\n Console.WriteLine($\"LCA of 4 and 5 is: {lca.Value}\");\n\n lca = tree.FindLCA(4, 3);\n Console.WriteLine($\"LCA of 4 and 3 is: {lca.Value}\");\n }\n}\n <\/pre>\n\uacb0\ub860<\/h2>\n