236. Lowest Common Ancestor of a Binary Tree

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 allowa 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.

Subscribe to see which companies asked this question

/** * 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 findNode(TreeNode* root, TreeNode* p,vector<TreeNode*>& v) { if(root==p || root==NULL) { if(root==NULL) return false; v.push_back(root); return true; } else { v.push_back(root); if(findNode(root->left,p,v)==true) return true; if(findNode(root->right,p,v)==true) return true; v.pop_back(); return false; } } public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==NULL) return NULL; vector<TreeNode*> v1; vector<TreeNode*> v2; findNode(root,p,v1); findNode(root,q,v2); int i= min(v1.size()-1,v2.size()-1); for(;i>=0;--i) { if(v2[i]==v1[i]) break; } return v1[i]; } };

修改：

更快捷的做法：

/** * 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==p||root==q||root==NULL) return root; TreeNode* leftR=lowestCommonAncestor(root->left,p,q); TreeNode* righR=lowestCommonAncestor(root->right,p,q); if(leftR!=NULL && righR!=NULL) //一般情况 return root; else return leftR?leftR:righR; //从上往下考虑，第一个遇到的非NULL即t为它的root。主要是考虑一个是另一个的祖先 } };