# 求二叉树的最低公共祖先

1啊，因为1的左子树中有7、而1的右子树中有8啊。

```
`#ifndef THELAST_COM_PARENT_H`
`#define THELAST_COM_PARENT_H`
`#include"reconstructBinaryTree.h"`
`bool isInsubTree(TreeNode *node,int n_val); `
`TreeNode *lastestCommParent(TreeNode *root,int n_val1 ,int n_val2){`
`	if(root==NULL){`
`		return NULL; `
`	}`
`	if(isInsubTree(root->left,n_val1)&&isInsubTree(root->right,n_val2)){`
`		return root;  `
`	}`
`	if(isInsubTree(root->left,n_val2)&&isInsubTree(root->right,n_val1)){`
`		return root; `
`	}`
`	if(isInsubTree(root->left,n_val1)&&isInsubTree(root->left,n_val2)){`
`		return lastestCommParent(root->left,n_val1,n_val2); `
`	}`
`	if(isInsubTree(root->right,n_val1)&&isInsubTree(root->right,n_val2)){`
`		return lastestCommParent(root->right,n_val1,n_val2); `
`	}`
`}`
`bool isInsubTree(TreeNode *node,int n_val){`
`	if(node==NULL){`
`		return false; `
`	}`
`	if(node->val==n_val){`
`		return true;`
`	}`
`    return  isInsubTree(node->left,n_val)||isInsubTree(node->right,n_val); `
`}`

`#endif `

```
```
`bool isInsubTree(TreeNode *node,int n_val)`
`这个函数的目的是确定n_val有没有在以node为根的子树中，如果在返回为true，否则返回false.`

```
```
`//如果n_val1和n_val2分别在左右子树中，那正好。`
`if(isInsubTree(root->left,n_val1)&&isInsubTree(root->right,n_val2)){`
`		return root;  `
`	}`
`	if(isInsubTree(root->left,n_val2)&&isInsubTree(root->right,n_val1)){`
`		return root; `
`	}`
`        //如果两个节点都在左子树中，那么往左树中走`
`	if(isInsubTree(root->left,n_val1)&&isInsubTree(root->left,n_val2)){`
`		return lastestCommParent(root->left,n_val1,n_val2); `
`	}`
`        //如果两个节点都在右子树中，那么往右子树走`
`	if(isInsubTree(root->right,n_val1)&&isInsubTree(root->right,n_val2)){`
`		return lastestCommParent(root->right,n_val1,n_val2); `
`	}`

```

http://fancyseeker.com/?p=301

```
`bool isInsubTree(TreeNode *node,int n_val){`
`	if(node==NULL){`
`		return false; `
`	}`
`	if(node->val==n_val){`
`		return true;`
`	}`
`    //这里只能这么写，因为我们只要出现一个true只写了啊，也就是这个节点只要出现一次就OK了，于是用“或”`
`    //要认真考虑递归的返回值，确保下一给的结果能反馈给上一给的程序，这样一级级从上往上返回，直到第一级`
`    //第一级也就是直接影响我们整个程序返回值的。`
`    return  isInsubTree(node->left,n_val)||isInsubTree(node->right,n_val); `
`}`

```

## 二叉树求两节点最低公共祖先，求随意两节点距离

-------1.求最低公共祖先LCA( Lowest Common Ancestor ) 什么是最低公共祖先?例如以下图.2与3的LCA是1:1与4的LCA是1:4与5的LCA是2. 那么给定两个节点n1和n2,如今要找出它们的LCA,怎样找?首先分析一下,n1和n2有几种情况?第一种.n1和n2分别在一个节点的左右子树中,比方4和5,LCA就是2,5和6,LCA就是1.2和3,LCA就是1:另外一种.n1和n2都在左子树或右子树,比方2和4,LCA就是2,1和4.LCA就是1. 一共这两种情