题解 | #二叉搜索树的最近公共祖先#
二叉搜索树的最近公共祖先
https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f
保存路径法
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param p int整型 * @param q int整型 * @return int整型 */ #define Maxsize 20 struct TreeNode** getpath(struct TreeNode* p,int target,int* count){ struct TreeNode** path = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*Maxsize); int j = 0; for(int i = 0;i<Maxsize;i++){ path[i] = (struct TreeNode*)malloc(sizeof(struct TreeNode)); } while(p->val!=target){ path[j] = p; if(p->val<target) p = p->right; else p = p->left; j++; } path[j] = p; *count = j; return path; } int lowestCommonAncestor(struct TreeNode* root, int p, int q ) { // write code here int count1 = 0; int count2 = 0; struct TreeNode** path1 = getpath(root,p,&count1); struct TreeNode** path2 = getpath(root,q,&count2); int resul; for(int i = 0;i<=count1&&i<=count2;i++){ if(path1[i]->val == path2[i]->val) resul = path1[i]->val; else break; } return resul; }