用数学归纳法证明：
首先对n=1时，对于二叉查找树，只有一个结点，也就是根结点，这时无法旋转，因此有0(n-1)种可能的旋转，命题成立。
假设对于n=k（k>1）时，对于二叉查找树，有k-1种可能的旋转。
那么对于n=k+1时，也就是我们在原来的二叉查找树中添加了一个结点，这个结点最终一定是二叉查找树的一个叶结点，其父结点一定存在（k>1），这个叶结点可能是其父结点的左子结点，也可能是其父结点的右子结点。如果是左子结点，那么相对于原二叉查找树，增加了一个右旋操作；如果是右子结点，那么增加了一个左旋的操作。这样加上原来的k-1种旋转可能，则对于有k+1个结点的新二叉查找树共有k种旋转可能。
这样我们就证明了上述归纳假设的正确性。

题目描述

给定一颗二叉搜索树，请找出其中的第k小的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

分析 

通过中序遍历列出节点顺序列表 

更加优化的解决办法是直接在遍历的时候将k值带进去O(k)-O(n)

import java.util.ArrayList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k) {
         if (pRoot == null) {
            return null;
         }
         ArrayList<TreeNode> list = new ArrayList<TreeNode>();
         inOrderTree(pRoot, list);
         if (list.size() < k || k == 0) {
            return null;
         } else {
            return list.get(k-1);
         }
     }

    private void inOrderTree(TreeNode pRoot, ArrayList<TreeNode> list) {
        if(pRoot == null) {
            return;
        }
        inOrderTree(pRoot.left, list);
        list.add(pRoot);
        inOrderTree(pRoot.right, list);
    }
}

O(k):



int cnt = 0;

TreeNode KthNode(TreeNode pRoot, int k) {
    if (pRoot == null)
        return null;
    TreeNode t = KthNode(pRoot.left, k);
    if (t != null)
        return t;
    if (++cnt < k)
        return KthNode(pRoot.right, k);
    else if (cnt == k)
        return pRoot;
    return null;
}

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>

using namespace std;

/*
问题:设计并实现一个算法，找出二叉树中某两个结点的第一个共同祖先。不得将额外的结点储存在另外的数据结构中。
     注意：这不一定是二叉查找树。
是否解出：解出，但不是最优
书上解法：
设两个结点为p,q
情况1：如果p,q在根节点的两侧，那么直接返回根节点(牛逼，没有想到利用根节点两侧结点的共同祖先就是根节点)，由于
情况2：如果p,q中有一个为根节点，则直接返回根节点(考虑到p,q在一条链上的情况，很关键)
由于从根节点一直向下做上述判断，就一定会进入情况1或情况2，从根节点向下，对每个结点进行上述处理，时间复杂度为O(N)

输入:
7(元素个数) 2(待寻找共同祖先的第一个结点的值) 5(待寻找共同祖先的第二个结点的值)
6 3 9 1 4 2 5(所有各个结点的值)
d(表示当前第1个结点有两个孩子，后续跟两个孩子结点下标) 2 3
d 4 5
z(表示当前第i个结点没有孩子结点)
r(表示当前第i个结点只有一个右孩子结点，后面跟该右孩子结点下标) 6
r 7
z
z

7 2 9
6 3 9 1 4 2 5
d 2 3
d 4 5
z
r 6
r 7
z
z
输出:
3(共同祖先的值，如果没有，返回NULL)
6

关键:
1 设两个结点为p,q
情况1：如果p,q在根节点的两侧，那么直接返回根节点(牛逼，没有想到利用根节点两侧结点的共同祖先就是根节点)，由于
情况2：如果p,q中有一个为根节点，则直接返回根节点(考虑到p,q在一条链上的情况，很关键)
由于从根节点一直向下做上述判断，就一定会进入情况1或情况2，从根节点向下，对每个结点进行上述处理，时间复杂度为O(N)
	//如果两个结点中有一个为根节点，直接返回该结点即可
	if(node1 == head)
	{
		return node1;
	}
	if(node2 == head)
	{
		return node2;
	}
	//如果两个结点分别位于根节点的两侧，则直接返回根节点
	bool isNode1OnLeft = isChildNode(head->_pLeft , node1);
	bool isNode2OnLeft = isChildNode(head->_pLeft , node2);
	if(isNode1OnLeft != isNode2OnLeft)
	{
		return head;
	}
	//如果两个结点位于根节点同一侧，则令根节点为其同一侧子树的根节点
	else
	{
		//如果都在根节点左侧
		if(isNode1OnLeft)
		{
			return findCommonAncestor(head->_pLeft, node1 , node2);
		}
		else
		{
			return findCommonAncestor(head->_pRight, node1 , node2);
		}
	}

2 判断一个结点A是否是某个结点P的子孙结点，如果结点等于P的左孩子结点或为P的右孩子结点，是；否则，
  从P的左孩子和右孩子分别为结点，继续搜索结点A是否为其孩子结点的孩子结点
//实际上应该是判断当前结点是否为某个节点的孩子结点
bool isChildNode(TreeNode* head , TreeNode* node)
{
	if(NULL == node)
	{
		return false;
	}
	//如果根节点都为空了，说明当前结点不是根节点的子孙结点
	if(NULL == head)
	{
		return false;
	}
	if(node == head)
	{
		return true;
	}
	else
	{
		//递归处理，注意如果一个结点都不在根节点的左右孩子结点中，那么这个结点必定不是根节点的子孙结点，这里用"||"
		return isChildNode(head->_pLeft , node) || isChildNode(head->_pRight , node);
	}
}

*/

typedef struct TreeNode
{
	TreeNode* _pLeft;
	TreeNode* _pRight;
	TreeNode* _pParent;
	int _value;
}TreeNode;
const int MAXSIZE = 10000;
int g_index;
TreeNode g_treeNodeArray[MAXSIZE];

TreeNode* createTreeNode()
{
	++g_index;
	g_treeNodeArray[g_index]._pLeft = g_treeNodeArray[g_index]._pRight = g_treeNodeArray[g_index]._pParent = NULL;
	return &g_treeNodeArray[g_index];
}

//建树
void buildTree(vector<int>& vecData)
{
	int size = vecData.size();
	g_index = 0;
	if(vecData.empty())
	{
		return;
	}
	string childFlag;
	int leftChild, rightChild;
	for(int i = 1 ; i <= size ; i++ )
	{
		cin >> childFlag;
		g_treeNodeArray[i]._value = vecData.at(i-1);
		if("d" == childFlag)
		{
			cin >> leftChild >> rightChild;
			g_treeNodeArray[i]._pLeft = &g_treeNodeArray[leftChild];
			g_treeNodeArray[leftChild]._pParent = &g_treeNodeArray[i];
			g_treeNodeArray[i]._pRight = &g_treeNodeArray[rightChild];
			g_treeNodeArray[rightChild]._pParent = &g_treeNodeArray[i];
		}
		else if("r" == childFlag)
		{
			cin >> rightChild;
			g_treeNodeArray[i]._pRight = &g_treeNodeArray[rightChild];
			g_treeNodeArray[rightChild]._pParent = &g_treeNodeArray[i];
		}
		else if("l" == childFlag)
		{
			cin >> leftChild;
			g_treeNodeArray[i]._pLeft = &g_treeNodeArray[leftChild];
			g_treeNodeArray[leftChild]._pParent = &g_treeNodeArray[i];
		}
	}
}

//根据结点值找到指定结点，如果同时出现多个结点的值与给定值相同，就返回最先找到的结点
TreeNode* findNode(TreeNode* head , int value)
{
	if(NULL == head)
	{
		return NULL;
	}
	if(value == head->_value)
	{
		return head;
	}
	TreeNode* leftChild = NULL;
	TreeNode* rightChild = NULL;
	if(head->_pLeft)
	{
		leftChild = findNode(head->_pLeft , value);
	}
	//在左子树找到，就直接返回结果；否则，递归查找右子树
	if(leftChild != NULL)
	{
		return leftChild;
	}
	else
	{
		if(head->_pRight)
		{
			return findNode(head->_pRight , value);
		}
		else
		{
			return NULL;
		}
	}
}

//寻找根节点
TreeNode* findRoot(TreeNode* node)
{
	if(NULL == node)
	{
		return NULL;
	}
	if(NULL == node->_pParent)
	{
		return node;
	}
	else
	{
		return findRoot(node->_pParent);
	}
}

//判断当前结点是位于根节点的哪一侧，关键是自底向上遍历还是自上向下遍历，应该是自上向下遍历，自下向上遍历不能指示方向
//实际上应该是判断当前结点是否为某个节点的孩子结点
bool isChildNode(TreeNode* head , TreeNode* node)
{
	if(NULL == node)
	{
		return false;
	}
	//如果根节点都为空了，说明当前结点不是根节点的子孙结点
	if(NULL == head)
	{
		return false;
	}
	if(node == head)
	{
		return true;
	}
	else
	{
		//递归处理，注意如果一个结点都不在根节点的左右孩子结点中，那么这个结点必定不是根节点的子孙结点，这里用"||"
		return isChildNode(head->_pLeft , node) || isChildNode(head->_pRight , node);
	}
}

//寻找两个结点的最近公共祖先，从上向下遍历
TreeNode* findCommonAncestor(TreeNode* head, TreeNode* node1 , TreeNode* node2)
{
	//鲁棒性
	if(NULL == head || NULL == node1 || NULL == node2)
	{
		return NULL;
	}
	//如果两个结点中有一个为根节点，直接返回该结点即可
	if(node1 == head)
	{
		return node1;
	}
	if(node2 == head)
	{
		return node2;
	}
	//如果两个结点分别位于根节点的两侧，则直接返回根节点
	bool isNode1OnLeft = isChildNode(head->_pLeft , node1);
	bool isNode2OnLeft = isChildNode(head->_pLeft , node2);
	if(isNode1OnLeft != isNode2OnLeft)
	{
		return head;
	}
	//如果两个结点位于根节点同一侧，则令根节点为其同一侧子树的根节点
	else
	{
		//如果都在根节点左侧
		if(isNode1OnLeft)
		{
			return findCommonAncestor(head->_pLeft, node1 , node2);
		}
		else
		{
			return findCommonAncestor(head->_pRight, node1 , node2);
		}
	}
}

void process()
{
	int nodeNum ; 
	int firstValue;
	int secondValue;
	int value;
	vector<int> vecData;
	while(cin >> nodeNum >> firstValue >> secondValue)
	{
		vecData.clear();
		for(int i = 0 ; i < nodeNum ; i++)
		{
			cin >> value;
			vecData.push_back( value );
		}
		//输入完成接下来需要建树
		buildTree(vecData);
		//建树完成后，就是寻找共同父节点
		TreeNode* root = findRoot(&g_treeNodeArray[1]);
		TreeNode* node1 = findNode(root , firstValue);
		TreeNode* node2 = findNode(root , secondValue);
		TreeNode* ancestorNode = findCommonAncestor(root , node1 , node2);
		if(ancestorNode)
		{
			cout << ancestorNode->_value << endl;
		}
		else
		{
			cout << "NULL" << endl;
		}
	}
}

int main(int argc , char* argv[])
{
	process();
	getchar();
	return 0;
}

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>

using namespace std;

/*
问题:设计并实现一个算法，找出二叉树中某两个结点的第一个共同祖先。不得将额外的结点储存在另外的数据结构中。
     注意：这不一定是二叉查找树。
分析:一种方式是根据结点，向上遍历，得到从当前结点到根节点的一个链表，设长链表的长度为L1,设短链表的长度为L2，
     将两个链表中较长的链表先走L1-L2步，然后寻找共同结点。
	 问题中说明：不得将结点额外存储。而采用链表的方式是需要额外存储结构的。如果不能用额外存储结构只能用这样的方式。
	 O(n^2)方法，设两个结点分别为n1,n2,
	 遍历n1,设当前结点为c,如果n1!=n2,令n2=n2->parent,

输入:
7(元素个数) 2(待寻找共同祖先的第一个结点的值) 5(待寻找共同祖先的第二个结点的值)
6 3 9 1 4 2 5(所有各个结点的值)
d(表示当前第1个结点有两个孩子，后续跟两个孩子结点下标) 2 3
d 4 5
z(表示当前第i个结点没有孩子结点)
r(表示当前第i个结点只有一个右孩子结点，后面跟该右孩子结点下标) 6
r 7
z
z

7 2 9
6 3 9 1 4 2 5
d 2 3
d 4 5
z
r 6
r 7
z
z
输出:
3(共同祖先的值，如果没有，返回NULL)
6
*/

typedef struct TreeNode
{
	TreeNode* _pLeft;
	TreeNode* _pRight;
	TreeNode* _pParent;
	int _value;
}TreeNode;
const int MAXSIZE = 10000;
int g_index;
TreeNode g_treeNodeArray[MAXSIZE];

TreeNode* createTreeNode()
{
	++g_index;
	g_treeNodeArray[g_index]._pLeft = g_treeNodeArray[g_index]._pRight = g_treeNodeArray[g_index]._pParent = NULL;
	return &g_treeNodeArray[g_index];
}

//建树
void buildTree(vector<int>& vecData)
{
	int size = vecData.size();
	g_index = 0;
	if(vecData.empty())
	{
		return;
	}
	string childFlag;
	int leftChild, rightChild;
	for(int i = 1 ; i <= size ; i++ )
	{
		cin >> childFlag;
		g_treeNodeArray[i]._value = vecData.at(i-1);
		if("d" == childFlag)
		{
			cin >> leftChild >> rightChild;
			g_treeNodeArray[i]._pLeft = &g_treeNodeArray[leftChild];
			g_treeNodeArray[leftChild]._pParent = &g_treeNodeArray[i];
			g_treeNodeArray[i]._pRight = &g_treeNodeArray[rightChild];
			g_treeNodeArray[rightChild]._pParent = &g_treeNodeArray[i];
		}
		else if("r" == childFlag)
		{
			cin >> rightChild;
			g_treeNodeArray[i]._pRight = &g_treeNodeArray[rightChild];
			g_treeNodeArray[rightChild]._pParent = &g_treeNodeArray[i];
		}
		else if("l" == childFlag)
		{
			cin >> leftChild;
			g_treeNodeArray[i]._pLeft = &g_treeNodeArray[leftChild];
			g_treeNodeArray[leftChild]._pParent = &g_treeNodeArray[i];
		}
	}
}

//根据结点值找到指定结点，如果同时出现多个结点的值与给定值相同，就返回最先找到的结点
TreeNode* findNode(TreeNode* head , int value)
{
	if(NULL == head)
	{
		return NULL;
	}
	if(value == head->_value)
	{
		return head;
	}
	TreeNode* leftChild = NULL;
	TreeNode* rightChild = NULL;
	if(head->_pLeft)
	{
		leftChild = findNode(head->_pLeft , value);
	}
	//在左子树找到，就直接返回结果；否则，递归查找右子树
	if(leftChild != NULL)
	{
		return leftChild;
	}
	else
	{
		if(head->_pRight)
		{
			return findNode(head->_pRight , value);
		}
		else
		{
			return NULL;
		}
	}
}

//寻找根节点
TreeNode* findRoot(TreeNode* node)
{
	if(NULL == node)
	{
		return NULL;
	}
	if(NULL == node->_pParent)
	{
		return node;
	}
	else
	{
		return findRoot(node->_pParent);
	}
}

//寻找两个结点的最近公共祖先，不使用额外的数据结构存放结点
TreeNode* findCommonAncestor(TreeNode* node1 , TreeNode* node2)
{
	TreeNode* tempNode2 = node2;
	TreeNode* tempNode1 = node1;
	while(tempNode2)
	{
		//遍历第一个结点链表，看是否找到与当前结点相同的结点
		while(tempNode1)
		{
			if(tempNode1->_value == tempNode2->_value)
			{
				return tempNode1;
			}
			else
			{
				tempNode1 = tempNode1->_pParent;
			}
		}
		//到这里就是把结点1所在链表的所有结点都遍历完，且没有找到共同祖先，此时就应该使得结点2等于结点2的父节点
		tempNode2 = tempNode2->_pParent;
		tempNode1 = node1;
	}

	//如果最终没有找到共同祖先，返回空
	return NULL;
}

void process()
{
	int nodeNum ; 
	int firstValue;
	int secondValue;
	int value;
	vector<int> vecData;
	while(cin >> nodeNum >> firstValue >> secondValue)
	{
		vecData.clear();
		for(int i = 0 ; i < nodeNum ; i++)
		{
			cin >> value;
			vecData.push_back( value );
		}
		//输入完成接下来需要建树
		buildTree(vecData);
		//建树完成后，就是寻找共同父节点
		TreeNode* root = findRoot(&g_treeNodeArray[1]);
		TreeNode* node1 = findNode(root , firstValue);
		TreeNode* node2 = findNode(root , secondValue);
		TreeNode* ancestorNode = findCommonAncestor(node1 , node2);
		if(ancestorNode)
		{
			cout << ancestorNode->_value << endl;
		}
		else
		{
			cout << "NULL" << endl;
		}
	}
}

int main(int argc , char* argv[])
{
	process();
	getchar();
	return 0;
}