关于leetcode236二叉树的公共最低祖先递归函数的语义问题？
来源：7-7 二分搜索树中的问题 Lowest Common Ancestor of a Binary Search Tree
triump
2018-10-27
老师：看了你github 上关于leetcode236 的代码如下：
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL)
return root;
if(root == p || root == q)
return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if(left != NULL && right != NULL)
return root;
if(left != NULL)
return left;
if(right != NULL)
return right;
return NULL;
}
};
感觉这个lowestCommonAncestor 函数的语义定义不是很清晰，可能是我理解的问题：比如 代码行： if(left != NULL && right != NULL) return root; 怎么最低公共祖先会在左右子树同时存在呢？
2回答
-
liuyubobobo
2018-10-29
赞思考！
首先，你补充的想法是没有问题的，可以实现一下试试看：）
其次，这里，我的方法中的函数语意定义确实很tricky：）这个函数的语意也是分情况讨论的，具体可以这么理解：
1）若以root为根的树中包含p,q两个结点，则返回p,q的最低公共祖先
2）若以root为根的树中只包含p或者q（中的一个），则返回root
3）若以root为根的树中既不包含p，又不包含q，则返回NULL
在这个定义下，if(left != NULL && right != NULL)的情况只有可能出现在root的一个子树包含p，另一个子树包含q的情况：）
注意，对于这个函数的语意定义，只在初始调用的时候，保证以root为根的树中，是肯定包含p和q这两个节点时适用。此时，在初始调用的时候，整个函数语意只取1)，可以解决这个问题。这一点在题目描述中已经有了保证，请参考题目描述中的最后Note部分：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ ：）
加油！：）
00 -
triump
提问者
2018-10-27
我感觉这个分成两个函数是不是会清楚点：1. 再重新定义个search(TreeNode * root, TreeNode *p, TreeNode *q, int &res) , 这个函数就是负责递归搜索p 和 q ，然后结果放进 res 里面. 2. 再定义一个lowestCommonAncestor 函数 调用search， 根据res 的结果 分情况处理
00
相似问题