学步园

题目：二叉树的结点定义如下：

struct TreeNode

{

    int m_nvalue;

    TreeNode* m_pLeft;

    TreeNode* m_pRight;

};

输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。

我的思路就是，普通的递归方式遍历二叉树，但是当遇到一个节点值相同时，如果为左子树则遍历右子树（当然此时另外一个函数处理），反之亦然。

网上看到的思路 相当不错

采用后序遍历，先判断左子树是否包含一个节点，然后判断右子树是否包含，最后判断当前节点是否包含。

只要3个中两个满足 就是最低的公共父节点，因为是后序遍历。

1. static bool lca(Node *root, int va, int vb, Node *&result, Node* parrent)  
2. {  
3.   // left/right 左/右子树是否含有要判断的两节点之一   
4.   bool left = false, right = false;  
5.   if (!result && root->left) left = lca(root->left,va,vb,result,root);  
6.   if (!result && root->right) right = lca(root->right,va,vb,result,root);  
7.   // mid 当前节点是否是要判断的两节点之一   
8.   bool mid = false;  
9.   if (root->data == va || root->data == vb) mid=true;  
10.   if (!result && int(left + right + mid) == 2) {  
11.     if (mid) result = parrent;  
12.     else result = root;  
13.   }  
14.   return left | mid | right ;  
15. }  
16.   
17. Node *lca(Node *root,int va, int vb)  
18. {  
19.   if (root == NULL) return NULL;  
20.   Node *result = NULL;  
21.   lca(root, va, vb,result, NULL);  
22.   return result;  
23. }