LeetCode: Lowest Common Ancestor of a Binary Tree Posted on May 17, 2018July 26, 2020 by braindenny Lowest Common Ancestor of a Binary Tree Similar Problems: Lowest Common Ancestor of a Binary Search Tree CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #classic, #manydetails, #recursive, #inspiring, #heightoftree, #lca 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).” Given the following binary search tree: root = [3,5,1,6,2,0,8,null,null,7,4] _______3______ / \ ___5__ ___1__ / \ / \ 6 _2 0 8 / \ 7 4 Example 1: Input: root, p = 5, q = 1 Output: 3 Explanation: The LCA of of nodes 5 and 1 is 3. Example 2: Input: root, p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution ## https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-tree ## Basic Ideas: recursive ## ## If exists in one subtree, return it. ## Otherwise, return the root ## ## Base condition: if root equals one, return root ## ## Complexity: Time O(n), Space O(1) # 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': # empty, or hit one if (not root) or root == p or root == q: return root r = self.lowestCommonAncestor(root.left, p, q) s = self.lowestCommonAncestor(root.right, p, q) # Find the nodes from both sub-tree if r and s: return root return r if not s else s Solution recursive // https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-tree // Basic Ideas: dfs // // Instead of searching both p and q, search one // // Complexity: Time O(n), Space O(h) /** * Definition for TreeNode. * type TreeNode struct { * Val int * Left *ListNode * Right *ListNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if root == nil { return nil } // found either one if root == p || root == q { return root } left := lowestCommonAncestor(root.Left, p, q) right := lowestCommonAncestor(root.Right, p, q) if left != nil && right != nil { return root } if left != nil { return left } else { return right } } Solution: Caculate the visit path // https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-tree // Basic Ideas: dfs // // Complexity: Time O(n), Space O(h) /** * Definition for TreeNode. * type TreeNode struct { * Val int * Left *ListNode * Right *ListNode * } */ func dfs(root *TreeNode, target *TreeNode, path *[]*TreeNode) bool { if root == nil { return false } // update path *path = append(*path, root) if root == target { return true } if dfs(root.Left, target, path) { return true } if dfs(root.Right, target, path) { return true } *path = (*path)[0:len(*path)-1] return false } func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { l1 := []*TreeNode{} dfs(root, p, &l1) l2 := []*TreeNode{} dfs(root, q, &l2) i := 0 for ; i<len(l1) && i<len(l2); i++ { if l1[i] != l2[i] { break } } return l1[i-1] } ## https://code.dennyzhang.com/lowest-common-ancestor-of-a-binary-tree ## Basic Ideas: recursive ## ## Notice: ## Here we assume p, q will exists in the tree ## ## Complexity: ? # 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 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) if left and right: return root return left if left else right Post Views: 4 Post navigation LeetCode: Add Bold Tag in StringLeetCode: String to Integer (atoi) Leave a Reply Cancel replyYour email address will not be published.Comment Name Email Website