leetcode 236. Lowest Common Ancestor of a Binary Tree(python)

题目

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).”

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, since a node can be a descendant of itself according to the LCA definition.

Note:

• All of the nodes’ values will be unique.
• p and q are different and both values will exist in the binary tree.

解法1：DFS

利用mid，left，right三个boolean变量代表当前节点为p，q中的一个，或者左子树或右子树中存在p和q中的node
算法流程

• 从根节点开始遍历整颗树
• 如果当前节点为p或q中的一个，那么将mid的值设为True然后继续搜索向下搜索当前节点的左子树和右子树
• left和right的值与mid一样，当recursion到某个level的时候，这个节点的mid值就是上层recursion结果的left和right，所以left和right即为recurse_tree的返回值
• 若mid，left，right这三个值的和大于等于2，证明当前节点即为我们要寻找的答案

class Solution(object):def __init__(self):self.ans = Nonedef lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""def recurse_tree(current_node):if not current_node:return Falseleft = recurse_tree(current_node.left)right = recurse_tree(current_node.right)mid = (current_node==p or current_node==q)if mid+left+right >= 2:self.ans = current_nodereturn mid or left or right

时间复杂度：O(N), N为节点的个数，因为最差的情况我们可能需要访问整颗树的所有节点
空间复杂度：O(N), N同样为节点的个数，因为这棵树的最大深度可以是N

二刷DFS1

二刷的时候看到一种非常intuitive但是比较慢的解法

class Solution {
    
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    while(root){
    // if both p and q are found in the left subtree, we need to look for the answer node in the left subtreeif(findNode(root->left,p->val) && findNode(root->left,q->val)){
    root = root->left;// if both p and q are found in the right subtree, we need to look for the answer node in the right subtree}else if(findNode(root->right,p->val) && findNode(root->right,q->val)){
    root = root->right;// if both of the two condition above is not true, means one of p,q is found in the left subtree and the other is found in the right subtree because p,q is guranteed to appear. So the current node is the answer we are looking for}else{
    break;}}return root;}// function to determine if target val appeared in the subtree of current nodebool findNode(TreeNode* node, int val){
    if(!node){
    return false;}if(node->val == val){
    return true;}return findNode(node->left,val) || findNode(node->right,val);}
};

二刷DFS2

二刷的dfs更加清晰一点

class Solution {
    
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(!root){
    return NULL;}// basic return condition: if the current node is p or q, return current node// it is also valid when the current node is the root, because p and q is guranteed to appear in the treeif(root->val == p->val || root->val == q->val){
    return root;}// if left is not null, meaning we have found p or q in the left subtreeTreeNode* left = lowestCommonAncestor(root->left,p,q);// if right is not null, meaning we have found p or q in the right subtreeTreeNode* right = lowestCommonAncestor(root->right,p,q);// if both left and right are not null, mean both p and q are found in the subtree because all the treenode values are unique. So the current node is the answerif(left && right){
    return root;}// if both left and right subtree does not founf anything, meaning no valid node found, return nullif(!left && !right){
    return NULL;}// otherwise, one of p or q is found in the left or right subtree || both p and q is found in the left or right subtree, return the not null nodeif(left){
    return left;}else{
    return right;}}
};

解法2：BFS+字典

在访问过程中，将每个节点的ancestor以字典形式进行储存，这样在字典中进行循环的搜索就能构成一个从children到一级级ancestor的有像图
算法流程
-从根节点开始遍历整棵树

• 将每个节点的ancestor储存在字典中，知道p和q都找到为止
• 一旦我们找到了p和q，将p的所有ancestors放入一个set中
• 循环的从q开始逆向寻找ancestors，直到找到一个q的ancestor node，这个node在p的ancestors set中出现过，那么这个节点就是我们想找的结果

class Solution(object):def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNode"""stack = [root]parent = {
    root:None}while p not in parent or q not in parent:node = stack.pop()if node.left:parent[node.left] = nodestack.append(node.left)if node.right:parent[node.right] = nodestack.append(node.right)ancestors = set()while p:ancestors.add(p)p = parent[p]while q not in ancestors:q = parent[q]return q

时间复杂度：O(N), N为节点的个数，因为最差的情况我们可能需要访问整颗树的所有节点
空间复杂度：O(N), N同样为节点的个数，因为这棵树的最大宽度可以是N

这边顺便补充一下DFS和BFS的空间复杂度，DFS的空间复杂度应该是树的最大深度，而BFS的最大深度应该是树的最大宽度

参考

leetcode官方solution

三刷

class Solution {
    
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(!root || root->val == p->val || root->val == q->val) return root;TreeNode* left = lowestCommonAncestor(root->left,p,q);TreeNode* right = lowestCommonAncestor(root->right,p,q);if(!left) return right;if(!right) return left;return root;}
};