Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1644.html
1644. Lowest Common Ancestor of a Binary Tree II
Level
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.valare unique. p != q
Solution
This problem is similar to 236-Lowest-Common-Ancestor-of-a-Binary-Tree, 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: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor( self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode' ) -> 'TreeNode': def dfs(root, p, q): if root is None: return False l = dfs(root.left, p, q) r = dfs(root.right, p, q) nonlocal ans if l and r: ans = root if (l or r) and (root.val == p.val or root.val == q.val): ans = root return l or r or root.val == p.val or root.val == q.val ans = None dfs(root, p, q) return ans -
/** * 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; };