Solution

Method 1 - Two Pass - Check Nodes Existence

Algorithm

Check if node p and q exists in Tree.
If either of them don't exist, return null.
Else return the LCA we used to to solve - Lowest Common Ancestor of a Binary Tree#Method 2 - Using Post-order Traversal 🏆.

Code

[{"language":"Java","code":"public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {\n\tboolean l = check(root, p);\n\tboolean k = check(root, q);\n\tif(!l || !k) {\n\t\treturn null;\n\t}\n\treturn dfs(root, p, q);\n}\nprivate boolean check(TreeNode root, TreeNode p) {\n\tif(root == null) {\n\t\treturn false;\n\t}\n\t\n\tif(root == p) {\n\t\treturn true;\n\t}\n\t\n\treturn check(root.left, p) || check(root.right, p);\n}\n\npublic TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {\n    if(root == null || root == p || root == q) {\n\t    return root;\n\t}\n\tTreeNode left = dfs(root.left, p, q);\n\tTreeNode right = dfs(root.right, p, q);\n\tif (left != null && right != null) {\n\t\treturn root;\n\t}\n\treturn left != null ? left : right;\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> TreeNode </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">lowestCommonAncestor</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(TreeNode root, TreeNode p, TreeNode q) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\tboolean</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> l </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> check</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(root, p);</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\tboolean</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> k </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> check</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(root, q);</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\tif</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">!</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">l </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">||</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> !</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">k) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\t\treturn</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> null</span><span style=\"color:#24292E;--shiki-

Related Tags