a node to be a descendant of itself<\/b>).\u201d<\/p>\n _______3______\n \/ \\\n ___5__ ___1__\n \/ \\ \/ \\\n 6 _2 0 8\n \/ \\\n 7 4\n<\/pre>\nFor example, the lowest common ancestor (LCA) of nodes 5<\/code> and 1<\/code> is 3<\/code>. Another example is LCA of nodes 5<\/code> and 4<\/code> is 5<\/code>, since a node can be a descendant of itself according to the LCA definition.<\/p>\n\u601d\u8def1<\/h3>\n
\u627e\u4e24\u4e2a\u8282\u70b9\u7684\u516c\u5171\u6700\u5c0f\u7956\u5148\uff0c\u53ef\u4ee5\u5229\u7528\u9012\u5f52\u7684\u601d\u60f3\uff0c\u5373\u5047\u8bbe\u6211\u4eec\u6709\u4e2a\u51fd\u6570\uff0c\u80fd\u5224\u65adroot\u4e3a\u6839\u8282\u70b9\u7684\u5b50\u6811\u91cc\u6709\u51e0\u4e2a\u7b26\u5408\u7684\u8282\u70b9\uff080\uff0c1\u62162\u4e2a\uff09\uff0c\u5728\u9012\u5f52\u8df3\u51fa\u7684\u8fc7\u7a0b\u4e2d\uff0c\u4e00\u65e6\u6211\u4eec\u53d1\u73b0\u6709\u8fd4\u56de2\u4e2a\u8282\u70b9\u7684\uff0c\u90a3\u8fd9\u4e2a\u6839\u5143\u7d20\u5c31\u80af\u5b9a\u662fp\u548cq\u7684\u6700\u4f4e\u516c\u5171\u8282\u70b9\u4e86\u3002<\/p>\n
\u601d\u8def2<\/h3>\n
\u5047\u8bbe\u8981\u627e\u7684\u8282\u70b9\u662f5\u548c1\uff0c\u90a3\u4e48\u4ece\u6839\u8282\u70b9\u901a\u5f805\u7684\u8def\u5f84\u662f3->5\uff0c\u901a\u5f801\u7684\u8def\u5f84\u662f3->1\u3002\u53ef\u4ee5\u7528\u9012\u5f52\u65b9\u6cd5\u6784\u9020\u4e00\u4e2a\u8def\u5f84\u6808\uff0c\u6bd4\u8f83\u5bb9\u6613\u5730\u627e\u5230\u8def\u5f84\uff0c\u7136\u540e\u5c31\u53d8\u6210\u4e24\u6761\u8def\u5f84\u7684\u6700\u957f\u516c\u5171\u8282\u70b9\u7684\u95ee\u9898\u4e86\uff0c\u201c\u5206\u5c94\u201d\u7684\u5730\u65b9\u5c31\u662fLCA.
\n\u76f8\u6bd4\u601d\u8def1\uff0c\u8fd9\u4e2a\u65b9\u6cd5\u5b9e\u65bd\u8d77\u6765\u7b80\u5355\u4e00\u4e9b\uff0c\u4f46\u662f\u8981\u904d\u5386\u4e24\u904d\u6811\uff0c\u4f1a\u7a0d\u5fae\u6162\u4e00\u70b9\u3002<\/p>\n
\u4ee3\u78011<\/h3>\n* struct TreeNode {\n * int val;\n * TreeNode *left;\n * TreeNode *right;\n * TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n * };\n *\/\nclass Solution {\npublic:\n int LCASub(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode*& retNode){\n \/\/If we find p or q, return 1\n \/\/If we find root contains p and q, return 2 and set the retNode to common node\n \/\/Else return 0\n if(root == NULL)\n return 0;\n int leftRet = LCASub(root->left, p, q, retNode);\n if(leftRet == 2)\n return 2;\n int rightRet = LCASub(root->right, p, q, retNode);\n if(rightRet == 2){\n return 2;\n }\n if(leftRet + rightRet == 2){\n retNode = root;\n return 2;\n } else if(root == p || root == q){\n if(leftRet==1 || rightRet == 1){\n retNode = root;\n return 2;\n } else {\n return 1;\n }\n } else {\n return leftRet + rightRet;\n }\n }\n TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {\n TreeNode* retVal = NULL;\n LCASub(root, p, q, retVal);\n return retVal;\n }\n};<\/pre>\n\u4ee3\u78012<\/h3>\nclass Solution {\npublic:\n bool getPath(TreeNode* root, TreeNode* p, stack<TreeNode*>& path){\n \/\/Get path from root to p\n \/\/If not available, return false\n if(root == NULL || root == p){\n path.push(root);\n return true;\n }\n bool foundPath = false;\n if(root->left != NULL){\n \/\/try left\n foundPath = getPath(root->left, p, path);\n if(foundPath){\n \/\/Mission complete, push current node and return\n path.push(root);\n return true;\n }\n }\n if(root->right != NULL){\n foundPath = getPath(root->right, p, path);\n if(foundPath){\n path.push(root);\n return true;\n }\n }\n return false;\n }\n TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {\n stack<TreeNode*> pPath;\n stack<TreeNode*> qPath;\n getPath(root, p, pPath);\n getPath(root, q, qPath);\n TreeNode* result = NULL;\n while(!pPath.empty() && !qPath.empty()){\n if(pPath.top() != qPath.top())\n break;\n result = pPath.top();\n pPath.pop();\n qPath.pop();\n }\n return result;\n }\n};<\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: \u201cThe lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66,133,205],"class_list":["post-1989","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj","tag-133","tag-205"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1989","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1989"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1989\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1989"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1989"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1989"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}