查找任意两个节点的公共父节点的整理
/*基本思路是对需要查找的节点赋权值为1，其它节点权值为0.那么只要找到一个节点的左右权值都不为1的点就是需要查找的公共父节点。 */static?class?Node?{ ??????????String?value; ??????????Node?left; ??????????Node?right; ??????} ??????static?Node?parent; ??????public?static?int?findParent(Node?root,?Node?first,?Node?second)?{ ??????????if?(root?==?null?||?parent?!=?null)?{ ??????????????//?Accelerate?check ??????????????return?0; ??????????} ??????????int?value?=?0; ??????????if?(root?==?first?||?root?==?second)?{ ??????????????//?find?the?node ??????????????value?=?1; ??????????} ??????????value?+=?findParent(root.left,?first,?second); ??????????value?+=?findParent(root.right,?first,?second); ??????????if?(value?==?2)?{ ??????????????//?find?the?common?parent?of?the?first?and?second?node ??????????????parent?=?root; ??????????????value?=?0; ??????????} ??????????return?value; ??????}??/*这种方法可以推广到查到n个节点的公共父节点，对每一个需要查找的节点赋值为1即可 *//**************************************************************************************//*二叉树上任意两个节点的最近公共父节点/*这个问题有LCA算法但是我还是使用的是递归的解法，后序遍历*/static bool lca(node *root, int va, int vb, node *&result, node *parent)?{ int left, right, mid; left = right = mid = 0; ? //判断左右子树是否有要寻找的节点 if (root->left) left = lca(root->left, va, vb, result, root); if (root->right) right = lca(root->right, va, vb, result, root); //判断当前节点是否是要找的结点 if (root->data == va || root->data == vb) { mid = 1; } if (!result && 2 == left + right + mid ) { if(mid) { result = parent; }? result = root; } return left || right || mid;}/*************************************************************************************/判断二叉树中两个节点的最低共同父节点 只要找到这样一个节点：已知的两个节点一个在它的左边子树，一个在它的右边子树；或者这个节点就是已知的两个节点中的一个，而另一个恰好在它的下面。*/TREE* CommonFather(TREE *root, TREE *A, TREE *B){?? ?if(root == NULL)?? ??? ?return root;?? ?if(root == A)//如果找到A，则后面的都不再找了，如果其他分支没找到B，则B必定在A下面?? ??? ?return A;?? ?if(root == B)//同上?? ??? ?return B;?? ?TREE *leftChild == NULL;?? ?TREE *rightChild == NULL;?? ?leftChild = CommonFather(root->left, A, B);//返回A，B或结果?? ?rightChild = CommonFather(root->right, A, B);//返回A，B或结果?? ?if(leftChild != NULL && rightChild != NULL)//如果都不为空，则必定一个是A，一个是B；?? ??? ?return root;?? ?if(leftChild != NULL)//如果不为空，则必定是A或B或结果；?? ??? ?return leftChild;?? ?if(rightChild != NULL)?? ??? ?return rightChild;//如果不为空，则必定是A或B或结果；}/**********整理到最后********************************************************/TreeNode * getLCA(TreeNode *root,TreeNode *A,TreeNode *B){if(root==NULL) returm NULL ;if(root==A || root==B) return root ;TreeNode *letf=getLCA(root->left , A, B) ;TreeNode *right=getLCA(root->right , A, B) ;if(left==NULL) return right ;else if(right==NULL) reurn left ;else reurn root ;}?