Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the : “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.
方法：递归。如果root为空或者root为p或者q节点，那么直接返回root。递归求左右子树中是否有p和q的最近公共祖先。如果左右子树递归求得的结果均不为空，那么表示p和q分属左右子树，直接返回root，否则p和q均属于左子树或者右子树，那么返回递归求出来的结果。
-
/** * 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) return root; TreeNode * left =lowestCommonAncestor(root->left,p,q); TreeNode * right=lowestCommonAncestor(root->right,p,q); if(left&&right)//p和q分属root两边 return root; return left? left:right;//p和q只是位于左右子树之中的一个 }};