Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/236.html
236. Lowest Common Ancestor of a Binary Tree
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:
“The 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 a node to be a descendant of itself).”
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3.
Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
@tag-tree
Algorithm
The very simple idea is to see where the two values are compared with root:
- Both values are on the left, then LCA is on the left
- Both values are on the right, then LCA is on the right
- One on the left and one on the right means that LCA is the current root node
Code
-
import javafx.util.Pair; import java.util.Stack; public class Lowest_Common_Ancestor_of_a_Binary_Tree { public static void main(String[] args) { Lowest_Common_Ancestor_of_a_Binary_Tree out = new Lowest_Common_Ancestor_of_a_Binary_Tree(); Solution s = out.new Solution(); TreeNode root = new TreeNode(3); TreeNode p = new TreeNode(5); TreeNode q = new TreeNode(1); root.left = p; root.right = q; System.out.println(s.lowestCommonAncestor(root, p, q).val); TreeNode root2 = new TreeNode(1); TreeNode p2 = new TreeNode(2); root2.left = p2; System.out.println(s.lowestCommonAncestor(root2, p2, root2).val); } /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return null; } if (root == p || root == q) { // key is here, especially when p is parent of q or vice-versa return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) { return root; } else if (left == null && right == null) { return null; } else if (left == null && right != null) { return right; } else { // left != null && right == null return left; } } } // official oj solution https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/ class Solution { private TreeNode ans; public Solution() { // Variable to store LCA node. this.ans = null; } private boolean recurseTree(TreeNode currentNode, TreeNode p, TreeNode q) { // If reached the end of a branch, return false. if (currentNode == null) { return false; } // Left Recursion. If left recursion returns true, set left = 1 else 0 int left = this.recurseTree(currentNode.left, p, q) ? 1 : 0; // Right Recursion int right = this.recurseTree(currentNode.right, p, q) ? 1 : 0; // If the current node is one of p or q int mid = (currentNode == p || currentNode == q) ? 1 : 0; // If any two of the flags left, right or mid become True if (mid + left + right >= 2) { this.ans = currentNode; } // Return true if any one of the three bool values is True. return (mid + left + right > 0); } public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // Traverse the tree this.recurseTree(root, p, q); return this.ans; } } // official oj solution-2 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // Stack for tree traversal Deque<TreeNode> stack = new ArrayDeque<>(); // HashMap for parent pointers Map<TreeNode, TreeNode> parent = new HashMap<>(); parent.put(root, null); stack.push(root); // Iterate until we find both the nodes p and q while (!parent.containsKey(p) || !parent.containsKey(q)) { TreeNode node = stack.pop(); // While traversing the tree, keep saving the parent pointers. if (node.left != null) { parent.put(node.left, node); stack.push(node.left); } if (node.right != null) { parent.put(node.right, node); stack.push(node.right); } } // Ancestors set() for node p. Set<TreeNode> ancestors = new HashSet<>(); // Process all ancestors for node p using parent pointers. while (p != null) { ancestors.add(p); p = parent.get(p); } // The first ancestor of q which appears in // p's ancestor set() is their lowest common ancestor. while (!ancestors.contains(q)) q = parent.get(q); return q; } } class Solution_iteration { // Three static flags to keep track of post-order traversal. // Both left and right traversal pending for a node. // Indicates the nodes children are yet to be traversed. private int BOTH_PENDING = 2; // Left traversal done. private int LEFT_DONE = 1; // Both left and right traversal done for a node. // Indicates the node can be popped off the stack. private int BOTH_DONE = 0; public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { Stack<Pair<TreeNode, Integer>> stack = new Stack<Pair<TreeNode, Integer>>(); // Initialize the stack with the root node. stack.push(new Pair<TreeNode, Integer>(root, this.BOTH_PENDING)); // This flag is set when either one of p or q is found. boolean one_node_found = false; // This is used to keep track of the LCA. TreeNode LCA = null; // Child node TreeNode child_node = null; // We do a post order traversal of the binary tree using stack while (!stack.isEmpty()) { Pair<TreeNode, Integer> top = stack.peek(); TreeNode parent_node = top.getKey(); int parent_state = top.getValue(); // If the parent_state is not equal to BOTH_DONE, // this means the parent_node can't be popped off yet. if (parent_state != this.BOTH_DONE) { // If both child traversals are pending if (parent_state == this.BOTH_PENDING) { // Check if the current parent_node is either p or q. if (parent_node == p || parent_node == q) { // If one_node_found was set already, this means we have found // both the nodes. if (one_node_found) { return LCA; } else { // Otherwise, set one_node_found to True, // to mark one of p and q is found. one_node_found = true; // Save the current top element of stack as the LCA. LCA = stack.peek().getKey(); } } // If both pending, traverse the left child first child_node = parent_node.left; } else { // traverse right child child_node = parent_node.right; } // Update the node state at the top of the stack // Since we have visited one more child. stack.pop(); stack.push(new Pair<TreeNode, Integer>(parent_node, parent_state - 1)); // Add the child node to the stack for traversal. if (child_node != null) { stack.push(new Pair<TreeNode, Integer>(child_node, this.BOTH_PENDING)); } } else { // If the parent_state of the node is both done, // the top node could be popped off the stack. // Update the LCA node to be the next top node. if (LCA == stack.pop().getKey() && one_node_found) { LCA = stack.peek().getKey(); } } } return null; } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left == null) return right; if (right == null) return left; return root; } }
-
// OJ: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ // 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': if root is None or root == p or root == q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) return root if left and right else (left or right) ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ if not root: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root if root == p or root == q: return root if left: return left if right: return right return None
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if root == nil || root == p || root == q { return root } left := lowestCommonAncestor(root.Left, p, q) right := lowestCommonAncestor(root.Right, p, q) if left == nil { return right } if right == nil { return left } return root }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function lowestCommonAncestor( root: TreeNode | null, p: TreeNode | null, q: TreeNode | null, ): TreeNode | null { const find = (root: TreeNode | null) => { if (root == null || root == p || root == q) { return root; } const left = find(root.left); const right = find(root.right); if (left != null && right != null) { return root; } if (left != null) { return left; } return right; }; return find(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) { if (!root || root == p || root == q) return root; const left = lowestCommonAncestor(root.left, p, q); const right = lowestCommonAncestor(root.right, p, q); if (!left) return right; if (!right) return left; return root; };
-
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; impl Solution { fn find( root: &Option<Rc<RefCell<TreeNode>>>, p: &Option<Rc<RefCell<TreeNode>>>, q: &Option<Rc<RefCell<TreeNode>>>, ) -> Option<Rc<RefCell<TreeNode>>> { if root.is_none() || root == p || root == q { return root.clone(); } let node = root.as_ref().unwrap().borrow(); let left = Self::find(&node.left, p, q); let right = Self::find(&node.right, p, q); match (left.is_some(), right.is_some()) { (true, false) => left, (false, true) => right, (false, false) => None, (true, true) => root.clone(), } } pub fn lowest_common_ancestor( root: Option<Rc<RefCell<TreeNode>>>, p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>, ) -> Option<Rc<RefCell<TreeNode>>> { Self::find(&root, &p, &q) } }