\uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 “\ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1” \ubb38\uc81c\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uace0, \ucf54\ud2c0\ub9b0\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \ub2e8\uacc4\ubcc4\ub85c \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\uc8fc\uc5b4\uc9c4 \uc774\uc9c4 \ud2b8\ub9ac\uc5d0\uc11c \ub450 \ub178\ub4dc A\uc640 B\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1(LCA, Lowest Common Ancestor)\uc744 \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc740 \ub450 \ub178\ub4dc\ub97c \ub3d9\uc2dc\uc5d0 \ud3ec\ud568\ud558\ub294 \uac00\uc7a5 \uae4a\uc740 \ub178\ub4dc\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4.<\/p>\n
\uc608\ub97c \ub4e4\uc5b4, \uc544\ub798\uc640 \uac19\uc740 \uc774\uc9c4 \ud2b8\ub9ac\uac00 \uc788\ub2e4\uace0 \uac00\uc815\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n
\n 1\n \/ \\\n 2 3\n \/ \\\n 4 5\n <\/pre>\n\uc774 \uacbd\uc6b0 \ub178\ub4dc 4\uc640 5\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc740 \ub178\ub4dc 2\uc785\ub2c8\ub2e4. \ub178\ub4dc 2\ub294 4\uc640 5\uc758 \ubd80\ubaa8 \ub178\ub4dc\uc774\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4.<\/p>\n
\uc785\ub825 \ud615\uc2dd<\/h2>\n
\uc785\ub825\uc73c\ub85c\ub294 \uc774\uc9c4 \ud2b8\ub9ac\uc758 \ub8e8\ud2b8 \ub178\ub4dc\uc640 \ub450 \uac1c\uc758 \ub178\ub4dc A\uc640 B\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. A\uc640 B\ub294 \ud2b8\ub9ac\uc758 \ub178\ub4dc \uc911 \ud558\ub098\uc785\ub2c8\ub2e4.<\/p>\n
\ucd9c\ub825 \ud615\uc2dd<\/h2>\n
\ucd9c\ub825\uc740 \ub178\ub4dc A\uc640 B\uc758 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1 \ub178\ub4dc\uc785\ub2c8\ub2e4.<\/p>\n
\ubb38\uc81c \ud574\uacb0 \uc804\ub7b5<\/h2>\n
\n
- \uc7ac\uadc0\uc801\uc778 \uc811\uadfc: \uc774\uc9c4 \ud2b8\ub9ac\uc758 \ud2b9\uc131\uc744 \uc774\uc6a9\ud558\uc5ec \ud2b8\ub9ac\ub97c \uc7ac\uadc0\uc801\uc73c\ub85c \ud0d0\uc0c9\ud569\ub2c8\ub2e4.<\/li>\n
- \uae30\uc800 \uc870\uac74: \ud604\uc7ac \ub178\ub4dc\uac00
null<\/code>\uc774\uac70\ub098 \ud604\uc7ac \ub178\ub4dc\uac00 A \ub610\ub294 B\uc77c \uacbd\uc6b0 \uadf8 \ub178\ub4dc\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li>\n- \uc7ac\uadc0 \ud638\ucd9c: \uc67c\ucabd \uc11c\ube0c\ud2b8\ub9ac\uc640 \uc624\ub978\ucabd \uc11c\ube0c\ud2b8\ub9ac\ub97c \uc7ac\uadc0\uc801\uc73c\ub85c \ud0d0\uc0c9\ud558\uac8c \ub429\ub2c8\ub2e4.<\/li>\n
- \uc870\uc0c1 \ud310\ub2e8: \uc67c\ucabd\uacfc \uc624\ub978\ucabd\uc5d0\uc11c \uac01\uac01 \ubc18\ud658\ub41c \ub178\ub4dc\uac00 \ubaa8\ub450
null<\/code>\uc774 \uc544\ub2d0 \uacbd\uc6b0 \ud604\uc7ac \ub178\ub4dc\uac00 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc785\ub2c8\ub2e4.<\/li>\n<\/ol>\n\ucf54\ub4dc \uad6c\ud604<\/h2>\n
\uc774\uc81c \uc704\uc758 \uc54c\uace0\ub9ac\uc998\uc744 \ucf54\ud2c0\ub9b0\uc73c\ub85c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\ndata class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)\n\nfun lowestCommonAncestor(root: TreeNode?, A: TreeNode?, B: TreeNode?): TreeNode? {\n \/\/ \uae30\uc800 \uc870\uac74\n if (root == null || root == A || root == B) {\n return root\n }\n\n \/\/ \uc67c\ucabd\uacfc \uc624\ub978\ucabd \uc11c\ube0c\ud2b8\ub9ac \ud0d0\uc0c9\n val left = lowestCommonAncestor(root.left, A, B)\n val right = lowestCommonAncestor(root.right, A, B)\n\n \/\/ \ud604\uc7ac \ub178\ub4dc\uac00 LCA\uc778 \uacbd\uc6b0\n return when {\n left != null && right != null -> root \/\/ \uc11c\ub85c \ub2e4\ub978 \uc11c\ube0c\ud2b8\ub9ac\uc5d0\uc11c \ubc1c\uacac\ub41c \uacbd\uc6b0\n left != null -> left \/\/ \uc67c\ucabd \uc11c\ube0c\ud2b8\ub9ac\uc5d0\uc11c\ub9cc \ubc1c\uacac\ub41c \uacbd\uc6b0\n right != null -> right \/\/ \uc624\ub978\ucabd \uc11c\ube0c\ud2b8\ub9ac\uc5d0\uc11c\ub9cc \ubc1c\uacac\ub41c \uacbd\uc6b0\n else -> null \/\/ \ubc1c\uacac\ub418\uc9c0 \uc54a\uc740 \uacbd\uc6b0\n }\n}\n <\/code><\/pre>\n\ucf54\ub4dc \uc124\uba85<\/h2>\n
\uc704\uc758 \ucf54\ub4dc\ub294 \ub2e4\uc74c\uc758 \uc8fc\uc694 \ubd80\ubd84\uc73c\ub85c \ub098\ub269\ub2c8\ub2e4:<\/p>\n
\n
data class TreeNode<\/code>: \uc774\uc9c4 \ud2b8\ub9ac\uc758 \ub178\ub4dc\ub97c \uc815\uc758\ud558\ub294 \ub370\uc774\ud130 \ud074\ub798\uc2a4\uc785\ub2c8\ub2e4.<\/li>\nlowestCommonAncestor<\/code>: \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1\uc744 \ucc3e\ub294 \uc7ac\uadc0 \ud568\uc218\uc785\ub2c8\ub2e4.<\/li>\n- \uae30\uc800 \uc870\uac74\uc744 \ud655\uc778\ud55c \ud6c4, \uc67c\ucabd \ubc0f \uc624\ub978\ucabd \uc11c\ube0c\ud2b8\ub9ac\ub97c \ud0d0\uc0c9\ud558\uace0, \uc870\uac74\uc5d0 \ub530\ub77c LCA\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubc0f \uacf5\uac04 \ubcf5\uc7a1\ub3c4<\/h2>\n
\uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N)\uc785\ub2c8\ub2e4. (N\uc740 \ub178\ub4dc\uc758 \uc218) \ubaa8\ub4e0 \ub178\ub4dc\ub97c \ud0d0\uc0c9\ud558\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4.<\/p>\n
\uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(H)\uc774\uba70, H\ub294 \ud2b8\ub9ac\uc758 \ub192\uc774\uc5d0 \ud574\ub2f9\ud569\ub2c8\ub2e4. \uc774\ub294 \uc7ac\uadc0 \ud638\ucd9c \uc2a4\ud0dd\uc5d0 \uc758\ud55c \uacf5\uac04 \uc0ac\uc6a9\ub7c9\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4.<\/p>\n
\uc608\uc81c \uc785\ub825 \ubc0f \ucd9c\ub825<\/h2>\n
\ub2e4\uc74c\uacfc \uac19\uc740 \uc785\ub825\uc744 \uace0\ub824\ud574\ubcfc \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n
\n \uc785\ub825:\n \ud2b8\ub9ac:\n 1\n \/ \\\n 2 3\n \/ \\\n 4 5\n A = 4\n B = 5\n\n \ucd9c\ub825:\n 2\n <\/pre>\n\uacb0\ub860<\/h2>\n
\uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \ucd5c\uc18c \uacf5\ud1b5 \uc870\uc0c1 \ubb38\uc81c\uc758 \uc815\uc758\uc640 \ud574\uacb0 \ubc29\ubc95\uc744 \ucf54\ud2c0\ub9b0\uc744 \ud1b5\ud574 \uc790\uc138\ud788 \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \ub2e4\uc591\ud55c \uc0c1\ud669\uc5d0\uc11c \uc790\uc8fc \ubc1c\uc0dd\ud558\ub294 \ubb38\uc81c\ub85c, \uc774\uc9c4 \ud2b8\ub9ac\uc758 \ud0d0\uc0c9 \uae30\uc220\uc744 \uc775\ud788\uc2e0\ub2e4\uba74 \ub9ce\uc740 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370 \ub3c4\uc6c0\uc774 \ub420 \uac83\uc785\ub2c8\ub2e4.<\/p>\n