找到两个叶子节点的最低公共节点
思路：
1.若这棵树为二叉搜索树的话，根据特性，我们从根节点遍历，若两个叶子节点值都小于根节点值，则最低公共节点一定在左子树，都大于的话在右子树。当一个小于一个大于时，所到达的节点就是最低公共节点。
2.若这棵树有父指针，那么问题可以转化为求链表的第一个公共节点的问题。
3.若只是棵普通的二叉树，可以两次遍历树，找到根节点到叶子节点的路径并保存。再从路径中比较找出最后一个相同的节点。
代码：
list<TreeNode*> path;
bool GetNodePath(TreeNode* root, TreeNode* pNode, list<TreeNode*>& path)//找到根到所求节点的路径。
{
if (root == NULL)
return true;
path.push_back(root);
bool found = false;
if(!found)
{
found = GetNodePath(root->left, pNode, path);
}
if (!found)
{
found = GetNodePath(root->right, pNode, path);
}
if (!found)
path.pop_back();
return found;
}
TreeNode *GetLastCommonNode(list<TreeNode*> path1,list<TreeNode*> path2)//求两条路径的最后公共节点
{
list< TreeNode*>::iterator it1 = path1.begin();
list< TreeNode*>::iterator it2 = path2.begin();
TreeNode* plast = NULL;
while (it1 != path1.end() && it2 != path2.end())
{
if (*it1 == *it2)
plast = *it1;
it1++;
it2++;
}
return plast;
}
TreeNode* GetLastCommonParent(TreeNode* root, TreeNode* pNode, TreeNode* qNode)
{
if (root == NULL || pNode == NULL || qNode == NULL)
return NULL;
list<TreeNode*> path1;
list<TreeNode*> path2;
bool p=GetNodePath(root, pNode, path1);
bool q=GetNodePath(root, qNode, path2);
if (p && q)
{
return GetLastCommonNode(path1, path2);
}
return NULL;
}
数组的逆序对的个数
思路：
采用归并排序的思想，每次归并时用两个指针指向两个数组，比较大小，出现逆序对就将计数器+1.
代码：
void Merge(int arr[], int l, int mid, int r, int *cnt) //合并两个数组
{
int* help = new int[r - l + 1]; //辅助数组
int p1 = l;
int p2 = mid + 1;
int index = 0;
while (p1 <= mid && p2 <= r)
{
help[index++] = arr[p1] < arr[p2] ? arr[p1] : arr[p2];
if (arr[p1] > arr[p2])
{
(*cnt)+=mid-p1+1; //arr[p1]>arr[p2]时，因为p1后面到mid的数字递增，所以都是逆序的.
for (int i = p1; i <= mid; i++)
{
cout << arr[i] << ' ' << arr[p2] << endl;
}
p2++;
}
else
{
p1++;
}
}
while (p1 <= mid) //复制剩余的元素
{
help[index++] = arr[p1++];
}
while (p2 <= r)
{
help[index++] = arr[p2++];
}
for (int i = 0; i < r - l + 1; i++) //复制到原数组
{
arr[l + i] = help[i];
}
delete[] help;
}
void MergeSort(int arr[], int l, int r,int *cnt)
{
if (l == r)
return;
if (l < r)
{
int mid = (l + r) / 2;
MergeSort(arr, l, mid,cnt);
MergeSort(arr, mid + 1,r,cnt);
Merge(arr, l, mid, r,cnt);
}
}
int FindInversePairs(int arr[], int len)
{
int cnt = 0;
if (len <= 0 || arr == NULL)
{
return 0;
}
MergeSort(arr, 0, len - 1,&cnt);
return cnt;
}
第一个公共链表节点
思路：
1.从后往前找最后一个公共节点，但是单链表只能向前。最后遍历的节点却要最先访问，所以用两个栈来贮存源节点到尾节点的路径。需要辅助空间。
2.可以先遍历一次链表分别得到长度，让长的链表先走几步，然后一起运动，就可以同时到达公共节点。
代码：
ListNode* FirstCommonListNode(ListNode* head1, ListNode* head2)
{
if (head1 == NULL || head2 == NULL)
{
return NULL;
}
int len1 = 0;
int len2 = 0;
ListNode* p = head1;
while (p)
{
len1++;
p = p->next;
}
p = head2;
while (p)
{
len2++;
p = p->next;
}
if (len1 > len2)
{
for (int i = 0; i < len1 - len2; i++)
{
head1 = head1->next;
}
}
else if (len1 < len2)
{
for (int i = 0; i < len2 - len1; i++)
{
head2 = head2->next;
}
}
ListNode*p1 = head1;
ListNode* p2 = head2;
while (p1 && p2)
{
if (p1 == p2)
return p1;
else
{
p1 = p1->next;
p2 = p2->next;
}
}
return NULL;
}