Lowest Common Ancestor of a Binary Tree Total Accepted: 6162 Total Submissions: 23311 My Submissions Question Solution Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______3______ /\___5_____1__
/\/\ 6_208 / \ 7 4 For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition. 正确的做法： 检查一个节点是否同时包含需要检查的两个节点，如果包含那么继续检查他的左右孩子，如果孩子节点不同时包含这两个节点，那么根节点就是最小祖先节点 这里虽然遍历会带来很多重复的检查，但是这里可以很好的排出一种情况，就是子节点中有一些相同的节点数量
/** * 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) {TreeNode *result = NULL;findLCA(root, p, q, &result);return result;}private:bool findNode(TreeNode *root, TreeNode *p){if (root == NULL || p == NULL){return false;}if (root == p){return true;}return findNode(root->left, p) || findNode(root->right, p);}int findLCA(TreeNode *root, TreeNode *p, TreeNode *q, TreeNode **result){if (root == NULL){return 0;}if (root == p){if (findNode(root, q)){*result = root;return 2;}else{return 1;}}else if (root == q){if (findNode(root, p)){*result = root;return 2;}else{return 1;}}else{int left = findLCA(root->left, p, q, result);int right = 0;if (left != 2){right = findLCA(root->right, p, q, result);}if (left == 1 && right == 1){*result = root;}return left + right;}} };
这里首先是完成了一个常规的寻找最小父亲节点的算法，但是有一个测试样例没有办法通过，这里的思路是，从根节点开始查找到包含需要检测的节点的路径，最后变化为寻找最大公共节点的问题，但是如果出现重复的节点就不能想象哪个路径是正确的 如果数中有重复的node那么，必须寻找到最小的父亲节点
/** * 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 || p == NULL || q == NULL){return NULL;}vector<TreeNode *> path1;path1.clear();GetNodePath(root,p,path1);vector<TreeNode *> path2;path2.clear();GetNodePath(root,q,path2);return FoundCommon(path1,path2);}int GetNodePath(TreeNode *root,TreeNode *node,vector<TreeNode *> &path){if(root == NULL){return 0;}if(root->val == node->val){path.push_back(root);return 1;}int found = 0;path.push_back(root);found = GetNodePath(root->left,node,path);if(found == 1){return 1;}found = GetNodePath(root->right,node,path);if(found == 1){return 1;}else{path.pop_back();return 0;}}TreeNode * FoundCommon(vector<TreeNode *> path1,vector<TreeNode *> path2){if(path1.empty() || path2.empty() || path1[0] != path2[0]){return NULL;}int i = 1;int j = 1;TreeNode *Root = path1[0];while(i < path1.size() && j < path2.size()){if(path1[i]->val == path2[j]->val){Root = path1[i];i++;continue;}else{return Root;}}return Root;}};爱的力量大到可以使人忘记一切，却又小到连一粒嫉妒的沙石也不能容纳
