对于两个节点的最低父节点的定义可以分为两种情况（1）像5和8最低公共父节点是3，两节点之间不存在父子关系（2）两节点存在父子关系，如5和4，最低公共父节点是5。 引用维基百科的话:The lowest common ancestor (LCA) is a concept in  and . Let T be a rooted  with n . The lowest common ancestor between two nodes v and w is defined 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 可以采用从顶往下的计算及先序遍历。也可以采用树的后续遍历来实现。相比较来说后续遍历更为简洁，时间复杂度最低为O(n)

Node *LCA(Node *root,Node *p,Node *q)

{

if(!root)

return NULL;

if(root==p||root==q)

return root;

Node *L=LCA(root->left,p,q);

Node *R=LCA(root->right,p,q);

if(L&&R)

return root;

return L?L:R;

}