二叉树的最近公共祖先
问题：
思路：
分治递归：
在二叉树中寻找节点p,q：要么p或q为根节点，在这种情况下，根节点即为最近公共祖先。要么p,q 分布在左子树或右子树中。若p,q分别分布在左右子树，根节点即为最近公共祖先，若p,q都处于左子树或右子树中，则处理对象变为根的左子树或右子树，对左子树或右子树递归求解。
递归函数的功能为寻找节点p,q的最近公共祖先，若根节点即为p或q，直接返回根节点，否则对左子树和右子树分别调用递归函数。若对左子树调用递归函数的返回值为空指针，表明p,q均在右子树中，返回对右子树调用递归函数的返回值（处理对象变为右子树，因为p,q均在右子树中）。若对右子树调用递归函数的返回值为空指针，表明p,q均在左子树中，返回对左子树调用递归函数的返回值（处理对象变为左子树，因为p,q均在左子树中）。若对左右子树调用递归函数的返回值均不为空，表明p,q分别处于左右子树中，此时根节点即为最近公共祖先，返回根节点。
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if( root==NULL || root==p || root==q )
return root;
TreeNode* left=lowestCommonAncestor( root->left,p,q );
TreeNode* right=lowestCommonAncestor( root->right,p,q );
if( left==NULL )
return right;
if( right==NULL )
return left;
return root;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153861.html
