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 _2 0 8
/ 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 { private: bool getPath(TreeNode* root,TreeNode* node,vector<TreeNode*>& path){ if(!root) { return false; } path.push_back(root); if(root == node){ return true; } bool is_found = getPath(root->left,node,path); if(!is_found){ is_found = getPath(root->right,node,path); } if(!is_found){ path.pop_back(); } return is_found; } public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { vector<TreeNode*>path_p,path_q; bool is_p_exist = getPath(root,p,path_p); bool is_q_exist = getPath(root,q,path_q); if(!is_p_exist || !is_q_exist){ return NULL; } if(p==q){ return p; } int i=0; for(;i<path_p.size() && i<path_q.size();i++){ if(path_p[i] != path_q[i]) { break; } } return path_p[i-1]; } };
Lowest Common Ancestor of a Binary Tree
原文：http://www.cnblogs.com/zengzy/p/5054246.html