235. Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
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).”
_______6______
/
___2__ ___8__
/ /
0 _4 7 9
/
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { while(root) { if (p->val > root->val && q->val > root->val) { root = root->right; continue; } if (p->val < root->val && q->val < root->val) { root = root->left; continue; } return root; } return NULL; }
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 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.
（1）一次递归找两个节点
TreeNode* lowestCommonAncestor02(TreeNode* root, TreeNode* p, TreeNode* q) { //return if found or not found, return NULL if not found if (root==NULL || root == p || root == q) return root; //find the LCA in left tree TreeNode* left = lowestCommonAncestor02(root->left, p, q); //find the LCA in right tree TreeNode* right = lowestCommonAncestor02(root->right, p, q); //left==NULL means both `p` and `q` are not found in left tree. if (left==NULL) return right; //right==NULL means both `p` and `q` are not found in right tree. if (right==NULL) return left; // left!=NULL && right !=NULL, which means `p` & `q` are seperated in left and right tree. return root; }
（2）分别记录根节点到所求节点的先序遍历路径，返回路径中最后一个相同的节点
bool findPath(TreeNode* root, TreeNode* p, vector<TreeNode*>& path) { if (root==NULL) return false; if (root == p) { path.push_back(p); return true; } path.push_back(root); if (findPath(root->left, p, path)) return true; if (findPath(root->right, p, path)) return true; path.pop_back(); return false; } //Ordinary way, find the path and comapre the path. TreeNode* lowestCommonAncestor01(TreeNode* root, TreeNode* p, TreeNode* q) { vector<TreeNode*> path1, path2; if (!findPath(root, p, path1)) return NULL; if (!findPath(root, q, path2)) return NULL; int len = path1.size() < path2.size() ? path1.size() : path2.size(); TreeNode* result = root; for(int i=0; i<len; i++) { if (path1[i] != path2[i]) { return result; } result = path1[i]; } return result; }