{"id":42,"date":"2026-04-05T16:01:57","date_gmt":"2026-04-05T08:01:57","guid":{"rendered":"https:\/\/blog.sjll.top\/?p=42"},"modified":"2026-04-05T16:01:57","modified_gmt":"2026-04-05T08:01:57","slug":"%e6%a0%91%e4%b8%8a%e6%90%9c%e7%b4%a2%e7%ae%97%e6%b3%95%e8%af%a6%e8%a7%a3%ef%bc%9ac%e4%ba%8c%e5%8f%89%e6%a0%91%e9%81%8d%e5%8e%86%e4%b8%8e%e6%9c%80%e8%bf%91%e5%85%ac%e5%85%b1%e7%a5%96%e5%85%88","status":"publish","type":"post","link":"https:\/\/www.sjll.top\/index.php\/2026\/04\/05\/%e6%a0%91%e4%b8%8a%e6%90%9c%e7%b4%a2%e7%ae%97%e6%b3%95%e8%af%a6%e8%a7%a3%ef%bc%9ac%e4%ba%8c%e5%8f%89%e6%a0%91%e9%81%8d%e5%8e%86%e4%b8%8e%e6%9c%80%e8%bf%91%e5%85%ac%e5%85%b1%e7%a5%96%e5%85%88\/","title":{"rendered":"\u6811\u4e0a\u641c\u7d22\u7b97\u6cd5\u8be6\u89e3\uff1aC++\u4e8c\u53c9\u6811\u904d\u5386\u4e0e\u6700\u8fd1\u516c\u5171\u7956\u5148"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">\u4ec0\u4e48\u662f\u6811\u4e0a\u641c\u7d22\uff1f<\/h2>\n\n\n\n<p><strong>\u6811\u4e0a\u641c\u7d22<\/strong> \u662f\u6307\u5728\u6811\u5f62\u6570\u636e\u7ed3\u6784\u4e0a\u8fdb\u884c\u641c\u7d22\u3001\u904d\u5386\u6216\u67e5\u627e\u7279\u5b9a\u8282\u70b9\u7684\u7b97\u6cd5\u3002\u6811\u662f\u4e00\u79cd\u91cd\u8981\u7684\u975e\u7ebf\u6027\u6570\u636e\u7ed3\u6784\uff0c\u5e7f\u6cdb\u5e94\u7528\u4e8e\u6587\u4ef6\u7cfb\u7edf\u3001DOM \u6811\u3001\u7b97\u6cd5\u7ade\u8d5b\u7b49\u573a\u666f\u3002<\/p>\n\n\n\n<p>\u5e38\u89c1\u7684\u6811\u4e0a\u641c\u7d22\u5305\u62ec\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>\u6811\u7684\u904d\u5386<\/strong>\uff1a\u524d\u5e8f\u3001\u4e2d\u5e8f\u3001\u540e\u5e8f\u3001\u5c42\u5e8f<\/li><li><strong>\u8282\u70b9\u67e5\u627e<\/strong>\uff1a\u67e5\u627e\u7279\u5b9a\u8282\u70b9\u6216\u7279\u5b9a\u6761\u4ef6\u7684\u8282\u70b9<\/li><li><strong>\u8def\u5f84\u67e5\u627e<\/strong>\uff1a\u627e\u5230\u4e24\u4e2a\u8282\u70b9\u4e4b\u95f4\u7684\u8def\u5f84<\/li><li><strong>\u6700\u8fd1\u516c\u5171\u7956\u5148\uff08LCA\uff09<\/strong>\uff1a\u627e\u5230\u4e24\u4e2a\u8282\u70b9\u7684\u6700\u8fd1\u516c\u5171\u7956\u5148<\/li><\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">\u6811\u7684\u8868\u793a\u65b9\u6cd5<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\">#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;queue&gt;\nusing namespace std;\n\n\/\/ \u6811\u8282\u70b9\u7ed3\u6784\nstruct TreeNode {\n    int val;\n    vector&lt;TreeNode*&gt; children;\n    TreeNode* left;   \/\/ \u7528\u4e8e\u4e8c\u53c9\u6811\n    TreeNode* right;  \/\/ \u7528\u4e8e\u4e8c\u53c9\u6811\n    \n    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n};\n\n\/\/ \u90bb\u63a5\u8868\u8868\u793a\uff08\u7528\u4e8e\u4e00\u822c\u6811\uff09\nvector&lt;vector&lt;int&gt;&gt; tree_adj;\n\n\/\/ \u4e8c\u53c9\u6811\u7684\u5efa\u7acb\uff08\u57fa\u4e8e\u6570\u7ec4\uff09\nTreeNode* build_binary_tree(const vector&lt;int&gt;&amp; arr) {\n    if (arr.empty() || arr[0] == -1) return nullptr;\n    \n    vector&lt;TreeNode*&gt; nodes;\n    for (int x : arr) {\n        nodes.push_back(x == -1 ? nullptr : new TreeNode(x));\n    }\n    \n    int n = arr.size();\n    for (int i = 0; i &lt; n; i++) {\n        if (nodes[i]) {\n            int left_idx = 2 * i + 1;\n            int right_idx = 2 * i + 2;\n            if (left_idx &lt; n) nodes[i]-&gt;left = nodes[left_idx];\n            if (right_idx &lt; n) nodes[i]-&gt;right = nodes[right_idx];\n        }\n    }\n    \n    return nodes[0];\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u4e8c\u53c9\u6811\u7684\u641c\u7d22\u904d\u5386<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\">\/\/ \u524d\u5e8f\u904d\u5386\uff08\u6839-\u5de6-\u53f3\uff09\nvoid preorder(TreeNode* root) {\n    if (!root) return;\n    cout &lt;&lt; root-&gt;val &lt;&lt; \" \";\n    preorder(root-&gt;left);\n    preorder(root-&gt;right);\n}\n\n\/\/ \u4e2d\u5e8f\u904d\u5386\uff08\u5de6-\u6839-\u53f3\uff09\nvoid inorder(TreeNode* root) {\n    if (!root) return;\n    inorder(root-&gt;left);\n    cout &lt;&lt; root-&gt;val &lt;&lt; \" \";\n    inorder(root-&gt;right);\n}\n\n\/\/ \u540e\u5e8f\u904d\u5386\uff08\u5de6-\u53f3-\u6839\uff09\nvoid postorder(TreeNode* root) {\n    if (!root) return;\n    postorder(root-&gt;left);\n    postorder(root-&gt;right);\n    cout &lt;&lt; root-&gt;val &lt;&lt; \" \";\n}\n\n\/\/ \u5c42\u5e8f\u904d\u5386\uff08\u5e7f\u5ea6\u4f18\u5148\uff09\nvoid levelorder(TreeNode* root) {\n    if (!root) return;\n    queue&lt;TreeNode*&gt; q;\n    q.push(root);\n    \n    while (!q.empty()) {\n        TreeNode* node = q.front();\n        q.pop();\n        cout &lt;&lt; node-&gt;val &lt;&lt; \" \";\n        \n        if (node-&gt;left) q.push(node-&gt;left);\n        if (node-&gt;right) q.push(node-&gt;right);\n    }\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u8282\u70b9\u67e5\u627e\u4e0e\u8def\u5f84<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\">\/\/ \u5728\u4e8c\u53c9\u6811\u4e2d\u67e5\u627e\u503c\u4e3a target \u7684\u8282\u70b9\nTreeNode* find_node(TreeNode* root, int target) {\n    if (!root) return nullptr;\n    if (root-&gt;val == target) return root;\n    \n    TreeNode* left = find_node(root-&gt;left, target);\n    if (left) return left;\n    \n    return find_node(root-&gt;right, target);\n}\n\n\/\/ \u67e5\u627e\u4ece\u6839\u5230\u76ee\u6807\u8282\u70b9\u7684\u8def\u5f84\nbool find_path(TreeNode* root, int target, vector&lt;int&gt;&amp; path) {\n    if (!root) return false;\n    \n    path.push_back(root-&gt;val);\n    \n    if (root-&gt;val == target) return true;\n    \n    if (find_path(root-&gt;left, target, path)) return true;\n    if (find_path(root-&gt;right, target, path)) return true;\n    \n    path.pop_back();  \/\/ \u56de\u6eaf\n    return false;\n}\n\n\/\/ \u67e5\u627e\u4e24\u4e2a\u8282\u70b9\u7684\u6700\u8fd1\u516c\u5171\u7956\u5148\uff08LCA\uff09\nTreeNode* find_lca(TreeNode* root, TreeNode* p, TreeNode* q) {\n    if (!root || root == p || root == q) return root;\n    \n    TreeNode* left = find_lca(root-&gt;left, p, q);\n    TreeNode* right = find_lca(root-&gt;right, p, q);\n    \n    if (left &amp;&amp; right) return root;\n    return left ? left : right;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u4e00\u822c\u6811\u7684\u641c\u7d22\uff08\u90bb\u63a5\u8868\uff09<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\">vector&lt;int&gt; tree_find_path(int n, const vector&lt;vector&lt;int&gt;&gt;&amp; adj, int start, int target) {\n    vector&lt;int&gt; parent(n, -1);\n    queue&lt;int&gt; q;\n    q.push(start);\n    parent[start] = start;\n    \n    while (!q.empty()) {\n        int u = q.front();\n        q.pop();\n        \n        if (u == target) break;\n        \n        for (int v : adj[u]) {\n            if (parent[v] == -1) {\n                parent[v] = u;\n                q.push(v);\n            }\n        }\n    }\n    \n    \/\/ \u8fd8\u539f\u8def\u5f84\n    vector&lt;int&gt; path;\n    if (parent[target] == -1) return path;  \/\/ \u65e0\u8def\u5f84\n    \n    for (int v = target; v != start; v = parent[v]) {\n        path.push_back(v);\n    }\n    path.push_back(start);\n    reverse(path.begin(), path.end());\n    \n    return path;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u5b8c\u5168\u5b9e\u73b0\u793a\u4f8b<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\">int main() {\n    \/\/ \u6784\u5efa\u4e8c\u53c9\u6811:     1\n    \/\/              \/   \\\n    \/\/             2     3\n    \/\/            \/ \\   \\\n    \/\/           4   5   6\n    \n    vector&lt;int&gt; arr = {1, 2, 3, 4, 5, -1, 6};\n    TreeNode* root = build_binary_tree(arr);\n    \n    cout &lt;&lt; \"\u524d\u5e8f\u904d\u5386: \";\n    preorder(root);   \/\/ \u8f93\u51fa: 1 2 4 5 3 6\n    cout &lt;&lt; endl;\n    \n    cout &lt;&lt; \"\u4e2d\u5e8f\u904d\u5386: \";\n    inorder(root);    \/\/ \u8f93\u51fa: 4 2 5 1 3 6\n    cout &lt;&lt; endl;\n    \n    cout &lt;&lt; \"\u540e\u5e8f\u904d\u5386: \";\n    postorder(root);  \/\/ \u8f93\u51fa: 4 5 2 6 3 1\n    cout &lt;&lt; endl;\n    \n    cout &lt;&lt; \"\u5c42\u5e8f\u904d\u5386: \";\n    levelorder(root); \/\/ \u8f93\u51fa: 1 2 3 4 5 6\n    cout &lt;&lt; endl;\n    \n    \/\/ \u67e5\u627e\u8def\u5f84\n    vector&lt;int&gt; path;\n    find_path(root, 5, path);\n    cout &lt;&lt; \"\u4ece\u6839\u5230\u8282\u70b95\u7684\u8def\u5f84: \";\n    for (int v : path) cout &lt;&lt; v &lt;&lt; \" \";\n    cout &lt;&lt; endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u590d\u6742\u5ea6\u5206\u6790<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table><thead><tr><th>\u64cd\u4f5c<\/th><th>\u65f6\u95f4\u590d\u6742\u5ea6<\/th><th>\u7a7a\u95f4\u590d\u6742\u5ea6<\/th><\/tr><\/thead><tbody><tr><td>\u524d\/\u4e2d\/\u540e\u5e8f\u904d\u5386<\/td><td>O(n)<\/td><td>O(h)\uff0ch\u4e3a\u6811\u9ad8<\/td><\/tr><tr><td>\u5c42\u5e8f\u904d\u5386<\/td><td>O(n)<\/td><td>O(w)\uff0cw\u4e3a\u6700\u5927\u5bbd\u5ea6<\/td><\/tr><tr><td>\u8282\u70b9\u67e5\u627e<\/td><td>O(n)<\/td><td>O(h)<\/td><\/tr><tr><td>LCA<\/td><td>O(n)<\/td><td>O(h)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">\u603b\u7ed3<\/h3>\n\n\n\n<p>\u6811\u4e0a\u641c\u7d22\u662f\u7b97\u6cd5\u7ade\u8d5b\u548c\u5de5\u7a0b\u5b9e\u8df5\u4e2d\u7684\u57fa\u7840\u6280\u80fd\u3002\u638c\u63e1\u5404\u79cd\u904d\u5386\u65b9\u5f0f\u3001\u7406\u89e3\u9012\u5f52\u4e0e\u56de\u6eaf\u7684\u601d\u60f3\uff0c\u5bf9\u4e8e\u89e3\u51b3\u66f4\u590d\u6742\u7684\u6811\u5f62\u95ee\u9898\uff08\u5982\u4e8c\u53c9\u641c\u7d22\u6811\u3001\u5e73\u8861\u6811\u3001\u7ebf\u6bb5\u6811\u7b49\uff09\u81f3\u5173\u91cd\u8981\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u4ec0\u4e48\u662f\u6811\u4e0a\u641c\u7d22\uff1f \u6811\u4e0a\u641c\u7d22 \u662f\u6307\u5728\u6811\u5f62\u6570\u636e\u7ed3\u6784\u4e0a\u8fdb\u884c\u641c\u7d22\u3001\u904d\u5386\u6216\u67e5\u627e\u7279\u5b9a\u8282\u70b9\u7684\u7b97\u6cd5\u3002\u6811\u662f\u4e00\u79cd\u91cd\u8981\u7684\u975e\u7ebf\u6027\u6570\u636e\u7ed3 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[53,55,60,59,58,56,57,54],"class_list":["post-42","post","type-post","status-publish","format-standard","hentry","category-3","tag-const-vector","tag-int-target","tag-return-false","tag-return-left","tag-return-nullptr","tag-return-root","tag-return-true","tag-clca"],"_links":{"self":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts\/42","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/comments?post=42"}],"version-history":[{"count":1,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts\/42\/revisions"}],"predecessor-version":[{"id":45,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts\/42\/revisions\/45"}],"wp:attachment":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/media?parent=42"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/categories?post=42"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/tags?post=42"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}