二叉树的最近公共祖先 （BSF和普通）

本文主要是介绍二叉树的最近公共祖先 （BSF和普通），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.若二叉树是一个搜索二叉树

看这个！https://blog.csdn.net/TheWise_lzy/article/details/99610262

从树的根节点开始和两个节点作比较，如果当前节点的值比两个节点的值都大，则这两个节点的最近公共祖先节点一定在该节点的左子树中，则下一步遍历当前节点的左子树；如果当前节点的值比两个节点的值都小，则这两个节点的最近公共祖先节点一定在该节点的右子树中，下一步遍历当前节点的右子树；这样直到找到第一个值是两个输入节点之间的值的节点，该节点就是两个节点的最近公共祖先节点。

Node* lowestCommonAncestor(Node* root,int p,int q) 
{if(!root)return NULL;else if((root->val > p && root->val < q)||(root->val < p && root->val > q))return root;else if(root->val==p||root->val==q)return root;else if(root->val > p && root->val > q)return lowestCommonAncestor(root->l,p,q);elsereturn lowestCommonAncestor(root->r,p,q);
}

 

2.若是一棵普通二叉树

从根节点开始遍历，如果node1和node2中的任一个和root匹配，那么root就是最低公共祖先。 如果都不匹配，则分别递归左、右子树，如果有一个 节点出现在左子树，并且另一个节点出现在右子树，则root就是最低公共祖先.  如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。 

Node* lowestCommonAncestor(Node* root,int p,int q) 
{if(root==NULL) return NULL;else if(root->val==p||root->val==q) return root;Node* left=lowestCommonAncestor(root->l,p,q);Node* right=lowestCommonAncestor(root->r,p,q);if(left!=NULL&&right!=NULL) return root;else if(left!=NULL) return left;else if(right!=NULL) return right;else return NULL;
}

 

这篇关于二叉树的最近公共祖先 （BSF和普通）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---