lowest_common_ancestor_of_a_binary_tree
1from utils import TreeNode 2 3 4# @leet start 5class Solution: 6 def lowestCommonAncestor( 7 self, root: TreeNode, p: TreeNode, q: TreeNode 8 ) -> TreeNode: 9 """ 10 This question asks us to find the lowest common ancestor of a binary 11 tree. Since it's not a binary search tree, we can't just split the 12 tree in half. Instead, we want to find the node where p and q are either 13 the node and in one of its subtrees, or in both of its subtrees. 14 15 To do so, we can recurse through the left and right subtrees, and 16 check if the current node is p or q. Finally, if left, mid, or right 17 are p or q, we can set the parent to our current candidate. 18 19 We continue going down the tree and make progress toward the parent candidate 20 until we can't anymore. 21 The recursion function needs to return if it contains one of the items 22 in its subtree, so it returns node == p or node == q or left or right. 23 """ 24 parent = None 25 26 def recurse(node): 27 nonlocal parent 28 if not node: 29 return False 30 left = recurse(node.left) 31 right = recurse(node.right) 32 mid = node == p or node == q 33 if [left, mid, right].count(True) >= 2: 34 parent = node 35 return mid or left or right 36 37 recurse(root) 38 return parent 39 40 41# @leet end 42 43 44def test(): 45 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def lowestCommonAncestor( 8 self, root: TreeNode, p: TreeNode, q: TreeNode 9 ) -> TreeNode: 10 """ 11 This question asks us to find the lowest common ancestor of a binary 12 tree. Since it's not a binary search tree, we can't just split the 13 tree in half. Instead, we want to find the node where p and q are either 14 the node and in one of its subtrees, or in both of its subtrees. 15 16 To do so, we can recurse through the left and right subtrees, and 17 check if the current node is p or q. Finally, if left, mid, or right 18 are p or q, we can set the parent to our current candidate. 19 20 We continue going down the tree and make progress toward the parent candidate 21 until we can't anymore. 22 The recursion function needs to return if it contains one of the items 23 in its subtree, so it returns node == p or node == q or left or right. 24 """ 25 parent = None 26 27 def recurse(node): 28 nonlocal parent 29 if not node: 30 return False 31 left = recurse(node.left) 32 right = recurse(node.right) 33 mid = node == p or node == q 34 if [left, mid, right].count(True) >= 2: 35 parent = node 36 return mid or left or right 37 38 recurse(root) 39 return parent
def
lowestCommonAncestor( self, root: utils.TreeNode, p: utils.TreeNode, q: utils.TreeNode) -> utils.TreeNode:
7 def lowestCommonAncestor( 8 self, root: TreeNode, p: TreeNode, q: TreeNode 9 ) -> TreeNode: 10 """ 11 This question asks us to find the lowest common ancestor of a binary 12 tree. Since it's not a binary search tree, we can't just split the 13 tree in half. Instead, we want to find the node where p and q are either 14 the node and in one of its subtrees, or in both of its subtrees. 15 16 To do so, we can recurse through the left and right subtrees, and 17 check if the current node is p or q. Finally, if left, mid, or right 18 are p or q, we can set the parent to our current candidate. 19 20 We continue going down the tree and make progress toward the parent candidate 21 until we can't anymore. 22 The recursion function needs to return if it contains one of the items 23 in its subtree, so it returns node == p or node == q or left or right. 24 """ 25 parent = None 26 27 def recurse(node): 28 nonlocal parent 29 if not node: 30 return False 31 left = recurse(node.left) 32 right = recurse(node.right) 33 mid = node == p or node == q 34 if [left, mid, right].count(True) >= 2: 35 parent = node 36 return mid or left or right 37 38 recurse(root) 39 return parent
This question asks us to find the lowest common ancestor of a binary tree. Since it's not a binary search tree, we can't just split the tree in half. Instead, we want to find the node where p and q are either the node and in one of its subtrees, or in both of its subtrees.
To do so, we can recurse through the left and right subtrees, and check if the current node is p or q. Finally, if left, mid, or right are p or q, we can set the parent to our current candidate.
We continue going down the tree and make progress toward the parent candidate until we can't anymore. The recursion function needs to return if it contains one of the items in its subtree, so it returns node == p or node == q or left or right.
def
test():