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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Given the following binary tree: root = [3,5,1,6,2,8,null,7,4] _______3______ / ___5__ ___1__ / / 6 _2 0 8 / 7 4 Example 1: Input: root = [3,4],p = 5,q = 1 Example 2: Input: root = [3,q = 4 Note:
Solution1: class Solution: def lowestCommonAncestor(self,root,p,q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ def judge(root,child): if not root or not child: return False if root==child: return True return judge(root.left,child) or judge(root.right,child) dic = collections.defaultdict(bool) if root is None: return None dic[root] = True dic[root.left] = judge(root.left,p) and judge(root.left,q) dic[root.right] = judge(root.right,p) and judge(root.right,q) if not dic[root.left] and not dic[root.right]: return root elif dic[root.left]: return self.lowestCommonAncestor(root.left,q) else: return self.lowestCommonAncestor(root.right,q) 29 / 31 test cases passed. Solution2: class Solution: def lowestCommonAncestor(self,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,q) #查看左子树中是否有目标结点,没有为null right = self.lowestCommonAncestor(root.right,q) #查看右子树是否有目标节点,没有为null if left is not None and right is not None: #都不为空,说明左右子树都有目标结点,则公共祖先就是本身 return root return left if left is not None else right #You‘d better use ‘left is not None‘ rather than ‘not left‘ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |