求解二叉树中两个节点的最近公共祖先（LCA）

蔚落 2022-08-22 01:30 243阅读 0赞

/************************************************************************/
    /* 
    非递归的方法
    
    下面是一个简单的复杂度为 O(n) 的算法，解决LCA问题
    
    1) 找到从根到n1的路径，并存储在一个向量或数组中。
    2)找到从根到n2的路径，并存储在一个向量或数组中。
    3) 遍历这两条路径，直到遇到一个不同的节点，则前面的那个即为最低公共祖先.
    
    */
    /************************************************************************/
    
    
    //二叉树节点
    struct Node
    {
    	int key;
    	Node *left, *right;
    };
    
    //找到从root到 节点值为key的路径,存储在path中。没有的话返回-1
    bool findpath(Node * root,vector<int> &path,int key)
    {
    	if(root == NULL) return false;
    	path.push_back(root->key);
    	if(root->key == key) return true;
    	//左子树或右子树 是否找到,找到的话当前节点就在路径中了
    	bool find =  ( findpath(root->left, path, key) || findpath(root->right,path ,key) );
    	if(find) return true;
    	//该节点下未找到就弹出
    	path.pop_back();
    	return false;
    }
    
    int findLCA(Node * root,int key1,int key2)
    {
    	vector<int> path1,path2;
    	bool find1 = findpath(root, path1, key1);
    	bool find2 = findpath(root, path2, key2);
    	if(find1 && find2)
    	{
    		int ans ;
    		for(int i=0; i < path1.size(); i++)
    		{
    			if(path1[i] != path2[i])
    			{
    				break;
    			}
    			else
    			{
    				ans = path1[i];
    			}
    		}
    		return ans;
    	}
    	return -1;
    }
    
    
    
    /************************************************************************/
    /* 
    递归求解方法
    
    从root开始遍历，如果n1和n2中的任一个和root匹配，那么root就是LCA。
    如果都不匹配，则分别递归左、右子树，
    如果有一个 key（n1或n2）出现在左子树，并且另一个key(n1或n2)出现在右子树，则root就是LCA.  
    如果两个key都出现在左子树，则说明LCA在左子树中，否则在右子树。
    */
    /************************************************************************/
    
    
    struct Node
    {
    	struct Node *left, *right;
    	int key;
    };
    
    // 返回n1和n2的 LCA的指针
    // 假设n1和n2都出现在树中
    struct Node *findLCA(struct Node* root, int n1, int n2)
    {
    	if (root == NULL) return NULL;
    
    	// 只要n1 或 n2 的任一个匹配即可
    	//  (注意：如果 一个节点是另一个祖先，则返回的是祖先节点。因为递归是要返回到祖先的 )
    	if (root->key == n1 || root->key == n2)
    		return root;
    	// 分别在左右子树查找
    	Node *left_lca  = findLCA(root->left, n1, n2);
    	Node *right_lca = findLCA(root->right, n1, n2);
    	// 如果都返回非空指针 Non-NULL, 则说明两个节点分别出现了在两个子树中，则当前节点肯定为LCA
    	if (left_lca && right_lca)  return root;
    	// 如果一个为空，在说明LCA在另一个子树
    	return (left_lca != NULL)? left_lca: right_lca;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，243人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java 求解二叉树的最近公共祖先

文章目录一、题目二、分析三、代码四、总结一、题目给定一个二叉树, 找到该树中两个指定节点的最近公

骑猪看日落/ 2023年01月19日 12:49/ 0 赞/ 40 阅读

相关最近公共祖先LCA

最近公共祖先（Lowest Common Ancestors，LCA）指有根树中距离两个节点最近的公共祖先。祖先指从当前节点到树根路径上的所有节点。 ![2021042810

蔚落/ 2023年01月17日 08:29/ 0 赞/ 204 阅读

相关二叉树的最近公共祖先

题目描述：给定一个二叉树，找到该树中两个指定节点的最近公共祖先。公共祖先的定义：对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x是p、q的祖先且

阳光穿透心脏的1/2处/ 2022年12月29日 05:00/ 0 赞/ 219 阅读

相关 leetcode---236. 二叉树的最近公共祖先(最近公共祖先)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是

矫情吗；*/ 2022年11月28日 00:42/ 0 赞/ 272 阅读

相关 Java 求解二叉搜索树的最近公共祖先

文章目录一、题目二、题解三、二叉树解法四、二叉搜索树解法五、迭代法六、总结

左手的ㄟ右手/ 2022年09月14日 14:27/ 0 赞/ 218 阅读

相关求解二叉树中两个节点的最近公共祖先（LCA）

// / 非递归的方法下面是一个简单的复杂度为 O(n) 的算法，解决LCA问题 1) 找到从根到n1的路径，并

蔚落/ 2022年08月22日 01:30/ 0 赞/ 244 阅读

相关 LCA 最近公共祖先

[https://www.cnblogs.com/JVxie/p/4854719.html][https_www.cnblogs.com_JVxie_p_4854719.htm

Myth丶恋晨/ 2022年06月02日 11:37/ 0 赞/ 231 阅读

相关二叉树的最近公共祖先

1、题目描述给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点

你的名字/ 2022年01月14日 05:41/ 0 赞/ 329 阅读

相关最近公共祖先（lca）与树上叉分

lca的定义不在过多解释，代码如下： inline void bfs() { queue<int>q; deep[s]=1

我不是女神ヾ/ 2021年11月29日 23:58/ 0 赞/ 328 阅读

相关二叉树的最近公共祖先

//给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 // // 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结

╰+攻爆jí腚メ/ 2021年06月22日 15:38/ 0 赞/ 497 阅读