{"id":3959,"date":"2018-09-14T01:59:07","date_gmt":"2018-09-14T08:59:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3959"},"modified":"2018-09-14T02:17:26","modified_gmt":"2018-09-14T09:17:26","slug":"leetcode-236-lowest-common-ancestor-of-a-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-236-lowest-common-ancestor-of-a-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 236. Lowest Common Ancestor of a Binary Tree"},"content":{"rendered":"<h1><strong>Problem<\/strong><\/h1>\n<p>Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.<\/p>\n<p>According to the\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Lowest_common_ancestor\" target=\"_blank\" rel=\"noopener\">definition of LCA on Wikipedia<\/a>: \u201cThe lowest common ancestor is defined between two nodes p\u00a0and q\u00a0as the lowest node in T that has both p\u00a0and q\u00a0as descendants (where we allow\u00a0<b>a node to be a descendant of itself<\/b>).\u201d<\/p>\n<p>Given the following binary tree:\u00a0 root =\u00a0[3,5,1,6,2,0,8,null,null,7,4]<\/p>\n<pre class=\"crayon:false\">        _______3______\r\n       \/              \\\r\n    ___5__          ___1__\r\n   \/      \\        \/      \\\r\n   6      _2       0       8\r\n         \/  \\\r\n         7   4\r\n<\/pre>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input:<\/strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1\r\n<strong>Output:<\/strong> 3\r\n<strong>Explanation: <\/strong>The LCA of of nodes <code>5<\/code> and <code>1<\/code> is <code>3.<\/code><\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false \"><strong>Input:<\/strong> root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4\r\n<strong>Output:<\/strong> 5\r\n<strong>Explanation: <\/strong>The LCA of nodes <code>5<\/code> and <code>4<\/code> is <code>5<\/code>, since a node can be a descendant of itself according to the LCA definition.<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li>All of the nodes&#8217; values will be unique.<\/li>\n<li>p and q are different and both values will\u00a0exist in the binary tree.<\/li>\n<\/ul>\n<h1>Solution 1: Recursion<\/h1>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(h)<\/p>\n<p>For a given root, recursively call LCA(root.left, p, q) and LCA(root.right, p, q)<\/p>\n<p>if both returns a valid node which means p, q are in different subtrees, then root will be their LCA.<\/p>\n<p>if only one valid node returns, which means p, q are in the same subtree, return that valid node as their LCA.<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {    \r\n    if (!root || root == p || root == q) return root;\r\n    TreeNode* l = lowestCommonAncestor(root-&gt;left, p, q);\r\n    TreeNode* r = lowestCommonAncestor(root-&gt;right, p, q);\r\n    if (l &amp;&amp; r) return root;\r\n    return l ? l : r;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\nclass Solution {\r\n  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {    \r\n    if (root == null || root == p || root == q) return root;\r\n    TreeNode l = lowestCommonAncestor(root.left, p, q);\r\n    TreeNode r = lowestCommonAncestor(root.right, p, q);\r\n    if (l == null || r == null) return l == null ? r : l;\r\n    return root;\r\n  }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true\"># Author: Huahua\r\nclass Solution:\r\n  def lowestCommonAncestor(self, root, p, q):    \r\n    if any((not root, root == p, root == q)): return root\r\n    l = self.lowestCommonAncestor(root.left, p, q)\r\n    r = self.lowestCommonAncestor(root.right, p, q)\r\n    if not l or not r: return l if l else r\r\n    return root<\/pre>\n<\/div><\/div>\n<h1><strong>Related Problems:<\/strong><\/h1>\n<ul>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-100-same-tree\/\">\u82b1\u82b1\u9171 Leetcode 100. Same Tree<\/a><\/li>\n<li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-865-smallest-subtree-with-all-the-deepest-nodes\/\">\u82b1\u82b1\u9171 LeetCode 865. Smallest Subtree with all the Deepest Nodes<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the\u00a0definition of LCA on Wikipedia:&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[406,177,17,28],"class_list":["post-3959","post","type-post","status-publish","format-standard","hentry","category-tree","tag-lca","tag-medium","tag-recursion","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3959","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3959"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3959\/revisions"}],"predecessor-version":[{"id":3966,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3959\/revisions\/3966"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3959"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3959"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3959"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}