[Leetcode] #236 Lowest Common Ancestor of a Binary Tree

Discription

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 

Solution

用两个数组分别存从根结点到输入的两个结点的路径，然后把问题转换成两个链表的最后公共结点。下面为两种写法，第一种找到路径就能退出，而第二种将所有路径搜索一遍，将符合要求的存下来。

class Solution { public: bool getPath(TreeNode* root, TreeNode* node, vector<TreeNode*> &path) { if (root == node) { path.push_back(root); return true; } path.push_back(root); if (root->left && getPath(root->left, node, path) || root->right && getPath(root->right, node, path)) return true; path.pop_back(); return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || !p || !q) return NULL; vector<TreeNode*> path1; vector<TreeNode*> path2; getPath(root, p, path1); getPath(root, q, path2); TreeNode *plast = NULL; for (int i = 0; i<path1.size() && i <path2.size(); i++) { if (path1[i] == path2[i]) plast = path1[i]; else break; } return plast; } }; class Solution { public: vector<TreeNode*> temp; void getPath(TreeNode *root, TreeNode *p, vector<TreeNode*> &path) { if (root == p) { path = temp; return; } temp.push_back(root); if (root->left) getPath(root->left, p, path); if (root->right) getPath(root->right, p, path); temp.pop_back(); } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { vector<TreeNode*> pathp, pathq; getPath(root, p, pathp); temp.clear(); getPath(root, q, pathq); int i = 1; while (i<pathp.size() && i<pathq.size()) { if (pathp[i] != pathq[i]) break; i++; } return pathp[i - 1]; } };

下面解法不是很懂，先记录下来。

class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == NULL) return NULL; if (root == p || root == q) return root; TreeNode* l1 = lowestCommonAncestor(root->left, p, q); TreeNode* l2 = lowestCommonAncestor(root->right, p, q); if (l1 != NULL && l2 != NULL) return root; return l1 == NULL ? l2 : l1; } };GitHub-Leetcode: https://github.com/wenwu313/LeetCode