236. Lowest Common Ancestor of a Binary Tree

方法1:

建立指向父节点的树；

struct Node{ Node* pre; Node* left; Node* right; TreeNode* cur; Node(TreeNode* root,Node* pre_root):cur(root),pre(pre_root){} }; class Solution { public: //建立包含指向父节点的树 void DFS(TreeNode* root,Node* pre_root) { if(root==NULL) return; Node* pre_left=new Node(root->left,pre_root); Node* pre_right=new Node(root->right,pre_root); pre_root->left=pre_left; pre_root->right=pre_right; DFS(root->left,pre_left); DFS(root->right,pre_right); } //目标节点在父节点树中的位置 void DFS_Node(Node* root,Node *&root_p,TreeNode* p) { if(root==NULL||root->cur==NULL) return; if(root->cur==p) { root_p=root; return; } DFS_Node(root->left,root_p,p); DFS_Node(root->right,root_p,p); } //根据父节点树找到从根节点到目标节点的路径 stack<TreeNode*> GetRoute(Node* root) { stack<TreeNode*> vec; while(root->pre!=NULL) { vec.push(root->cur); root=root->pre; } vec.push(root->cur); return vec; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(!root) return NULL; Node* pre_root=new Node(root,NULL); DFS(root,pre_root); Node* pre_p, *pre_q; DFS_Node(pre_root, pre_p, p); DFS_Node(pre_root, pre_q, q); stack<TreeNode*> res_p,res_q; res_p=GetRoute(pre_p); res_q=GetRoute(pre_q); TreeNode* top=NULL; while(!res_p.empty()&&!res_q.empty()) { if(res_p.top()!=res_q.top()) break; top=res_p.top(); res_p.pop(); res_q.pop(); } return top; } };

方法2:

分治法，查看节点是否在两颗子树中；

class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==NULL) return NULL; if(root==p||root==q)return root; TreeNode* left=lowestCommonAncestor(root->left, p, q); TreeNode* right=lowestCommonAncestor(root->right, p, q); if(left&&right) return root; return left==NULL?right:left; } };

方法3:

直接找到节点路径

class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==NULL||q==NULL||p==NULL) return NULL; vector<TreeNode*> vp,vq,res_p,res_q; vp.push_back(root); vq.push_back(root); GetPath(root, p,vp); GetPath(root, q,vq); TreeNode* lca=NULL; for(int i=0;i<vp.size()&&i<vq.size();i++) { if(vp[i]==vq[i])lca=vp[i]; else break; } return lca; } private: bool GetPath(TreeNode* root,TreeNode* p, vector<TreeNode*>& vt) { if(root==p) { return true; } if(root->left) { vt.push_back(root->left); if(GetPath(root->left, p, vt)) return true; vt.pop_back(); } if(root->right) { vt.push_back(root->right); if(GetPath(root->right, p, vt)) return true; vt.pop_back(); } return false; } };

其他：

http://arsenal591.blog.163.com/blog/static/253901269201510169448656/