##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1644.html

# 1644. Lowest Common Ancestor of a Binary Tree II

Medium

## Description

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique.

According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a binary tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)”. A descendant of a node x is a node y that is on the path from node x to some leaf node.

Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Output: 3

Explanation: The LCA of nodes 5 and 1 is 3.

Example 2: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: 5

Explanation: The LCA of nodes 5 and 4 is 5. A node can be a descendant of itself according to the definition of LCA.

Example 3: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10

Output: null

Explanation: Node 10 does not exist in the tree, so return null.

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q

## Solution

This problem is similar to problem #236, with the difference that node p and node q are not always in the binary tree.

First do depth first search on the binary tree to find the nodes p and q. If either node does not exist, return null.

If both p and q are in the binary tree, then do depth first search again to find the lowest common ancestor.

### Follow up: Can you find the LCA traversing the tree, without checking nodes existence?

DFS. If both nodes are in the tree, refer to problem 236-Lowest-Common-Ancestor-of-a-Binary-Tree.

During DFS, if the root is equal to p or q, it cannot immediately return the root like in problem 236-Lowest-Common-Ancestor-of-a-Binary-Tree because we cannot determine if the other node is in the tree. Therefore, our solution is to adopt post-order traversal to ensure that each node is visited. The logic is then the same as when both nodes are in the tree. Additionally, when we encounter p or q during the search, we keep a count. Finally, if the count equals 2, it means that both nodes have been found and we can return the answer.

• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode ancestor = null;
public TreeNode p = null, q = null;

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
findNodes(root, p, q);
if (p == null || q == null)
return null;
depthFirstSearch(root, p, q);
return ancestor;
}

public void findNodes(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return;
if (root == p)
this.p = p;
else if (root == q)
this.q = q;
findNodes(root.left, p, q);
findNodes(root.right, p, q);
}

public boolean depthFirstSearch(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return false;
boolean left = depthFirstSearch(root.left, p, q);
boolean right = depthFirstSearch(root.right, p, q);
if (left && right || ((root.val == p.val || root.val == q.val) && (left || right)))
ancestor = root;
return left || right || (root.val == p.val || root.val == q.val);
}
}

public class Solution_followup {

// 计数找到了p和q的多少个节点
private int count = 0;

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode res = lca(root, p, q);
// 如果都找到了，就可以返回res了，否则说明某个节点不存在，返回null
return count == 2 ? res : null;
}

// 功能是返回p与q都存在的情况下的lca
private TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}

// 在左右两边找p和q
TreeNode left = lca(root.left, p, q), right = lca(root.right, p, q);

// 如果当前树根就是p或q，那计数加1，并且root就是lca（在p和q都存在于树的情况下）
if (root == p || root == q) {
count++;
return root;
}

// 如果左子树里找不到p和q，那lca就在右边，如果右子树找不到p和q那lca就在左边，
// 否则就是左右都找到了，返回当前树根
if (left == null) {
return right;
} else if (right == null) {
return left;
} else {
return root;
}
}
}


• // OJ: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/
// Time: O(N)
// Space: O(H)
class Solution {
bool findPath(TreeNode *node, TreeNode *target, vector<TreeNode*> &path) {
if (!node) return false;
path.push_back(node);
if (node == target) return true;
if (findPath(node->left, target, path) || findPath(node->right, target, path)) return true;
path.pop_back();
return false;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> a, b;
findPath(root, p, a);
findPath(root, q, b);
TreeNode *ans = nullptr;
for (int i = 0; i < a.size() && i < b.size() && a[i] == b[i]; ++i) ans = a[i];
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

'''
>>> a = True
>>> a + 1 + 2
4

>>> a = 1
>>> b = None
>>> c = True
>>>
>>> a or b
1
>>> b or a
1
>>> b or c
True
>>> a or c
1
'''
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
self.res = None

def dfs(node):
if not node:
return 0
cur = (node == p or node == q)
left = dfs(node.left)
right = dfs(node.right)
if cur+left+right >= 2:
self.res = node
return cur or left or right
dfs(root)
return self.res

# without checking node existance
class Solution_followup:
def __init__(self):
self.count = 0

def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
res = self.lca(root, p, q)
return res if self.count == 2 else None

def lca(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if root is None:
return None

left = self.lca(root.left, p, q)
right = self.lca(root.right, p, q)

if root == p or root == q:
self.count += 1
return root

if left is None:
return right
elif right is None:
return left
else:
return root


• /**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function (root, p, q) {
const dfs = root => {
if (!root) {
return false;
}
const l = dfs(root.left);
const r = dfs(root.right);
if (l && r) {
ans = root;
}
if ((l || r) && (root.val === p.val || root.val === q.val)) {
ans = root;
}
return l || r || root.val === p.val || root.val === q.val;
};
let ans = null;
dfs(root);
return ans;
};