首页 > 试题广场 >

在二叉树中找到两个节点的最近公共祖先

[编程题]在二叉树中找到两个节点的最近公共祖先

热度指数：172938 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足 $1 \le n \le 10^5 \$ , 节点值val满足区间 [0,n)

要求：时间复杂度 $O(n)$

注：本题保证二叉树中每个节点的val值均不相同。

如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：

所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。

节点本身可以视为自己的祖先

示例1

输入

{3,5,1,6,2,0,8,#,#,7,4},5,1

输出

示例2

输入

{3,5,1,6,2,0,8,#,#,7,4},2,7

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python

奋斗的习习张

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# @param root TreeNode类 
# @param o1 int整型 
# @param o2 int整型 
# @return int整型
# 提交的代码都太难理解了，整个最好理解的！
class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        if not root:
            return None
        if root.val == o1&nbs***bsp;root.val == o2:
            return root.val
        array = []
        self.mid_order(root, array)
        index = array.index(root.val)
        left = array[:index]
        right = array[index+1:]
        if o1 in left and o2 in right&nbs***bsp;(o1 in right and o2 in left):
            return root.val
        if o1 in left and o2 in left:
            return self.lowestCommonAncestor(root.left, o1, o2)
        if o1 in right and o2 in right:
            return self.lowestCommonAncestor(root.right, o1, o2)
        return None
        
    def mid_order(self, root, array):
        if root.left:
            self.mid_order(root.left, array)
        array.append(root.val)
        if root.right:
            self.mid_order(root.right, array)

发表于 2021-11-07 22:26:55 回复(0)

Python

每天一通offercall

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 
# @param root TreeNode类 
# @param o1 int整型 
# @param o2 int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        #基本结束条件
        if not root:return None
        if root.val == o1 or root.val == o2:return root.val
        #递归,o1和o2要么在左子树,要么在右子树,要么分别在左右子树
        #left和right至多有一个是最近公共祖先,并可根据left和right判断o1和o2的位置关系
        left = self.lowestCommonAncestor(root.left, o1, o2)
        right = self.lowestCommonAncestor(root.right, o1, o2)
        #若left为None,说明o1,o2都不在左子树由题意即全在右子树(那么此时right即为最近公共祖先),right为None类似
        if not left:return right
        if not right: return left
        #若left,right全不为None,则o1,o2分别在左右子树,易知此时最近公共祖先即为root
        return root.val
        # write code here

发表于 2021-05-19 20:04:58 回复(0)

Python

猫牛

class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        return self.dfs(root, o1, o2).val
    
    def dfs(self, root, o1, o2):
        if not root or root.val == o1 or root.val == o2:
            return root
        
        left = self.dfs(root.left, o1, o2)
        right = self.dfs(root.right, o1, o2)
        if left is None:
            return right
        if right is None:
            return left
        
        return root

编辑于 2021-04-05 22:40:54 回复(0)

Python

穿着背带裤的鸡哥在唱跳Rap

【递归】C++或Python版：

基于公共祖先特点的递归做法

从根节点往下递归：

1. 若该节点是第一个值为o1或o2的节点，则该节点是最近公共祖先；

2. 否则，看左子树是否包含o1或o2：

2.1 若左子树包含o1或o2，则看右子树有没有：

a. 若右子树没有，则公共祖先在左子树

b. 若右子树有，则o1和o2肯定是左右子树一边一个，则公共祖先是根节点；

2.2 若左子树不包含o1和o2，则公共祖先在右子树或者该根子树不包含o1和o2。（两种情况都取决于右子树）

C++代码：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        return dfs(root,o1,o2)->val;
    }
    TreeNode* dfs(TreeNode* root, int o1,int o2){
        // 最近的节点
        if(root == nullptr || root-> val == o1 || root->val == o2) return root;
        
        // 如果左子树o1和o2都没有，则可能在右子树
                // 或者左右子树都没有,则root子树也没有
        TreeNode* left = dfs(root->left,o1,o2);
        if(left == nullptr) return dfs(root->right,o1,o2);
        
        // 如果左子树有o1或者o2，看右子树有没有
        TreeNode* right = dfs(root->right,o1,o2);
        if(right == nullptr) return left; // 如果右子树没有，则左子树肯定同时包含o1和o2
        
        // 如果左右子树都有，则肯定是一边一个
        return root;
    }
};

Python代码：

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 
# @param o1 int整型 
# @param o2 int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        return self.dfs(root,o1,o2).val
        
    # 该子树是否包含o1或o2
    def dfs(self,root,o1,o2):
        if root is None: 
            return  None
            
        if root.val == o1&nbs***bsp;root.val == o2: 
            return root
            
        left = self.dfs(root.left,o1,o2)
        # 左子树没有，则在右子树
                # 若右子树没有,则右子树返回 None
        if left == None: return self.dfs(root.right,o1,o2)

        # 左子树有，则看右子树有没有
        right = self.dfs(root.right,o1,o2)
        if right == None : return left
        
        # 左子树右子树都有,则最近的祖先节点是root
        return root

编辑于 2021-01-02 21:54:48 回复(3)

Python

我喜欢就好

凭啥python总是超时啊？

class Solution:
def lowestCommonAncestor(self , root , o1 , o2 ):
# write code here
if not root: return 0
if root.val == o1 or root.val == o2:
return root.val
l = self.lowestCommonAncestor(root.left, o1, o2)
r = self.lowestCommonAncestor(root.right, o1, o2)
if l == 0: return r
if r == 0: return l
return root.val

还有这种：

class Solution:
def lowestCommonAncestor(self , root , o1 , o2 ):
# write code here
# if not root: return None
def find(root, p, q):
if not root or root.val == p or root.val == q:
return root
l = find(root.left, p, q)
r = find(root.right, p, q)
if l and not r: return l
if not l and r: return r
return root
return find(root, o1, o2).val
都超时，我看C++他们也是这个思路？？？？？？？？？？？？？？？？？？？？？？？？？？？？？、

发表于 2020-11-10 10:09:31 回复(3)

Python

lishangru

class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        
        def helper(node):
            if not node or node.val == o1 or node.val == o2:
                return node
            left = helper(node.left)
            right = helper(node.right)
            if left and right:
                return node
            return left if left else right
        
        lca = helper(root)
        return lca.val if lca else -1

这个代码为什么超时了呢？

编辑于 2020-10-29 12:45:50 回复(1)

Python

七耀之心

python3果然超时贴一下代码和思路：先层序遍历，然后根据结果推两个目标节点的所有祖先，再找最近的。最近牛客网天天超时，贴别人AC的代码都超时，搞毛线

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 
# @param o1 int整型 
# @param o2 int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        queue = []
        output = []
        queue.append(root)
        output.append(root)
        while(len(queue) != 0):
            if queue[0] != '#':
                if queue[0].left != None:
                    queue.append(queue[0].left)
                    output.append(queue[0].left)
                else:
                    queue.append('#')
                    output.append('#')
            if queue[0] != '#':   
                if queue[0].right != None:
                    queue.append(queue[0].right)
                    output.append(queue[0].right)
                else:
                    queue.append('#')
                    output.append('#')               
            queue.pop(0)
        for i in range(len(output)):
            if output[i] != '#':
                if o1 == output[i].val:
                    a = i
                if o2 == output[i].val:
                    b = i
        a += 1
        b += 1
        c = []
        d = []
        while(a != 1):
            c.append(a)
            a = a // 2
        while(b != 1):
            d.append(b)
            b = b // 2
        c.append(1)
        d.append(1)
        for i in range(len(c)):
            for j in range(len(d)):
                if c[i] == d[j]:
                    return(output[c[i]-1].val)

发表于 2020-10-22 12:11:35 回复(2)