【数据结构】二叉树专题总结

专题主要内容：

• 二叉树的概念
• 二叉树的性质
• 二叉树存储方式
• 二叉树基本操作
• 二叉树经典面试题

前言：

树的定义：树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。

树具有的特点有：

• （1）每个结点有零个或多个子结点
• （2）没有父节点的结点称为根节点
• （3）每一个非根结点有且只有一个父节点
• （4）除了根结点外，每个子结点可以分为多个不相交的子树。

树的基本术语有：

• 若一个结点有子树，那么该结点称为子树根的“双亲”，子树的根称为该结点的“孩子”。有相同双亲的结点互为“兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
• 结点的度：结点拥有的子树的数目
• 叶子结点：度为0的结点
• 分支结点：度不为0的结点
• 树的度：树中结点的最大的度
• 层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1
• 树的高度：树中结点的最大层次
• 森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

存储方式:

大致分为四类：

• 双亲表示法，（不易找到孩子）
• 孩子表示法，（不易找到双亲）
• 双亲孩子表示法，（不确定孩子数量，易造成指针浪费）
• 孩子兄弟表示法（推荐）（解决指针浪费问题）

专题内容详解：

---

（一）二叉树的概念：

---

二叉树 是结点的有限集合，该集合或者为空，或者是由一个根节点加两棵分别称为左子树和右子树的的二叉树组成。
二叉树特点：

• 每个节点最多有两课子树，即二叉树不存在度大于2的结点
• 二叉树的子树有左右之分，其左右不能颠倒
  
  因此：二叉树就是通过上面五种形式的组合或者嵌套而成

满二叉树&完全二叉树

• 满二叉树：在一棵二叉树中，如果所有分支节点都存在左右字树，并且所有叶子节点都在用一层上。
• 完全二叉树：一棵具有N个节点的二叉树结构与慢二叉树前N个结点结构完全相同，就称为完全二叉树，即叶子节点在最后两层，最下一层叶子节点靠左，倒数第二层叶子结点靠右，如果一个节点只有一颗子树，那么这一定是左子树
  

---

（二）二叉树的性质：

---

• 性质1：二叉树第i层上的结点数目最多为2^(i-1)(i>=1)
• 性质2：深度为k的二叉树至多有(2^k)-1个结点（k>=1）
• 性质3：包含n个结点的二叉树的高度至少为(log2n)+1
• 性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
• 性质4的证明
  证明*：因为二叉树中所有结点的度数均不大于2，不妨设n0表示度为0的结点个数，n1表示度为1的结点个数，n2表示度为2的结点个数。三类结点加起来为总结点个数，于是便可得到：n=n0+n1+n2(1)由度之间的关系可得第二个等式：n=n0*0+n1*1+n2*2+1即n=n1+2n2+1(2)，将（1)（2）组合在一起可得到n0=n2+1
• 性质5：如果对一棵有n个结点的完全二叉树（其深度为[log2(n)]+1）的结点按层序编号(从第1层到底=第[log2(n)]+1层，每层从左到右)对任一结点i有：
  a、如果i=1，则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点[i/2]。
  b、如果2i>n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i。
  c、如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。
  

  ---

（三）二叉树存储方式：

---

顺序存储结构：就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系。下图所示的是完全二叉树，一般的二叉树，对于不存在的结点设置为”^”即可。但会对存储空间造成浪费，所以，顺序存储结构一般适用于完全二叉树。

顺序存储结构：二叉链表：二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域。

当增加一个指向其双亲的指针域，那么就称为三叉链表。

---

（四）二叉树基本操作：

---

创建与销毁：

声明：

typedef char BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* pLeft;
    struct BinaryTreeNode* pRight;
}BTNode,*pBTNode;

//创建二叉树
pBTNode BinaryTreeCreat(char* arr,int n,int* p);
//销毁二叉树
void BinaryTreeDestory(pBTNode* root);

参考代码：

//创建结点
static pBTNode BBuyNode(BTDataType x)
{
    pBTNode node = (pBTNode)malloc(sizeof(BTNode));
    assert(node);
    node->pLeft = NULL;
    node->data = x;
    node->pRight = NULL;
    return node;
}
//创建二叉树
pBTNode BinaryTreeCreat(char* arr, int n, int* p)
{
    if ((arr[*p] != '#') && ((*p) < n))
    {
        pBTNode root = BBuyNode(arr[(*p)]);
        ++(*p);
        root->pLeft = BinaryTreeCreat(arr, n, p);
        ++(*p);                                  
        root->pRight = BinaryTreeCreat(arr, n, p);
        return root;
    }
    else
    {
        return NULL;
    }
}
//销毁二叉树
void BinaryTreeDestory(pBTNode* root)
{
    pBTNode pCur = (*root);

    if (pCur)
    {
        BinaryTreeDestory(&pCur->pLeft);
        BinaryTreeDestory(&pCur->pRight);
        free(pCur);
        pCur = NULL;
    }

}

---

（五）二叉树经典面试题简单实现：

---

• 前序、中序、后序遍历（递归&非递归）
• 二叉树层次遍历
• 二叉树的结点个数
• 叶子结点个数
• 二叉树深度
• 二叉树第k层结点个数
• 判断一个结点是否在二叉树中
• 判断一棵二叉树树是否是完全二叉树
• 获取一个结点双亲结点
• 获取一个结点的左孩子结点
• 获取一个结点的右孩子结点
• 求二叉树的镜像(递归&非递归)
• 求二叉树中最远两个结点的距离
• 由前序和中序遍历序列重建二叉树 （前序序列：1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5）
• 求二叉树两个结点的最近公共祖先；
• 将二叉搜索树转化成有序的双向链表

参考代码：

//前中后递归遍历
void BinaryTreePrevSearch(pBTNode root)
{
    if (root == NULL)
        return;
    printf("%c  ",root->data);
    BinaryTreePrevSearch(root->pLeft);
    BinaryTreePrevSearch(root->pRight);
}
void BinaryTreeMiddleSearch(pBTNode root)
{
    if (root == NULL)
        return;
    BinaryTreePrevSearch(root->pLeft);
    printf("%c  ", root->data);
    BinaryTreePrevSearch(root->pRight);
}
void BinaryTreeLastSearch(pBTNode root)
{
    if (root == NULL)
        return;
    BinaryTreePrevSearch(root->pLeft);
    BinaryTreePrevSearch(root->pRight);
    printf("%c  ", root->data);

}

//层序遍历
void BinaryTreeLevelSearch(pBTNode root)
{
    Queue q;
    if (root == NULL)
    {
        return;
    }
    QueueInit(&q);

    QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        pBTNode front = QueueFront(&q);
        printf("%c ",front->data);
        QueuePop(&q);
        if (front->pLeft)
        {
            QueuePush(&q,front->pLeft);
        }
        if (front->pRight)
        {
            QueuePush(&q,front->pRight);
        }
    }
    printf("\n");
}

//前中后非递归遍历
//先访问每个结点（pCur&&pCur->pLeft）在压栈，，然后将右子树看成小型二叉树进行相同操作
void BinaryTreePrevSearch_OP(pBTNode root)
{
    Stack s;
    BTNode* pCur = root;
    StackInit(&s);

    if (root == NULL)
        return;
    //当前指针不为空或者栈不为空就应该继续
    while (pCur||!StackEmpty(&s))
    {
        while (pCur)
        {
            printf("%c ",pCur->data);
            StackPush(&s,pCur);
            pCur = pCur->pLeft;
        }
        pBTNode top = StackTop(&s);
        StackPop(&s);
        pCur = top->pRight;

    }

}
//每个结点（pCur&&pCur->pLeft）先压栈再访问，然后将右子树看成小型二叉树进行相同操作
void BinaryTreeMiddleSearch_OP(pBTNode root)
{
    Stack s;
    SatckInit(&s);

    pBTNode pCur = root;
    if (root == NULL)
        return;
    //当前指针不为空或者栈不为空就应该继续
    while (pCur || !StackEmpty(&s))
    {
        while (pCur)
        {
            StackPush(&s, pCur);
            pCur = pCur->pLeft;
        }
        pBTNode top = StackTop(&s);
        printf("%c   ",top->data);
        StackPop(&s);
        pCur = top->pRight;
    }
}
//当根节点存在，先使根节点入栈，若存在左子树，使左子树入栈，直到左子树的左子树为空停止；
//此时取栈顶top元素，判断栈顶元素的右子树top->right是否为空，若为空直接打印栈顶元素；
//若不为空,再以右子树为根节点继续上述判断(入栈，取栈顶等)；
//（此处假设top->right无左右子树）那么此节点会先入栈；
//入栈完毕后得知它的左子树为空，当即会判断右子树，右子树为空，打印栈顶元素，出栈。
//此时到达栈顶top，即打印top；但是应该加一个打印判断条件(top->right == ?),这个？就是top右子树；
//综上：在每次打印完毕后，将此节点用pre标记起来，即满足top->tight == pre即可！！！
//），的的pre记录上次栈顶的位置，
void BinaryTreeLastSearch_OP(pBTNode root)
{
    Stack s;
    pBTNode pCur = root;
    StackInit(&s);
    if (root == NULL)
        return;
    //当前指针不为空或者栈不为空就应该继续
    while (pCur || !StackEmpty(&s))
    {
        while (pCur)
        {
            StackPush(&s, pCur);
            pCur = pCur->pLeft;
        }

        pBTNode tmp = StackTop(&s);
        pBTNode pre = NULL;

        if (tmp->pRight == NULL||tmp->pRight == pre)
        {
            printf("%c ",tmp);
            StackPop(&s);
            pre = tmp;
        }
        else
        {
            pCur = tmp->pRight;

        }
    }
}

//二叉树的结点个数
int BinaryTreeNodeSize(pBTNode root)
{
    if (root == NULL)
        return 0;
    return  BinaryTreeNodeSize(root->pLeft)
        + BinaryTreeNodeSize(root->pRight) + 1;
}
//叶子结点个数
int BinaryTreeNodeLeaf(pBTNode root)
{
    if (root == NULL)
    {
        return 0;
    }
    if ((root->pLeft == NULL) && (root->pRight == NULL))
        return 1;
    return BinaryTreeNodeLeaf(root->pLeft)
        + BinaryTreeNodeLeaf(root->pRight);
}
//二叉树深度
int BinaryTreeDepth(pBTNode root)
{
    if (root == NULL)
        return 0;
    int left = BinaryTreeDepth(root->pLeft);
    int right = BinaryTreeDepth(root->pRight);

    return (left>right) ? (left+1) : (right+1);
}
//二叉树第k层结点个数
int BinaryTreeNodeKLevel(pBTNode root, int k)
{                                                
    if (root == NULL)
        return 0;
    if (k == 1)
        return 1;
    return BinaryTreeNodeKLevel(root->pLeft, k - 1)
        + BinaryTreeNodeKLevel(root->pRight, k - 1);
}
//判断一个结点是否在二叉树中
pBTNode BinaryTreeFind(pBTNode root, BTDataType x)
{
    pBTNode ret;
    if (root == NULL || root->data == x)
        return root;
    ret = BinaryTreeFind(root->pLeft,x);
    if (ret)
        return ret;
    ret = BinaryTreeFind(root->pRight,x);
    if (ret)
        return ret;
    return NULL;

}

//判断一棵二叉树树是否是完全二叉树
bool BinaryTreeComplete(pBTNode root)
{

    Queue q;

    if (root == NULL)
        return true;
    QueueInit(&q);

    QueuePush(&q,root);
    while (!QueueEmpty(&q))
    {
        pBTNode tmp = QueueFront(&q);
        QueuePop(&q);
        if (tmp == NULL)
        {
            while (!QueueEmpty(&q))
            {
                QueuePop(&q);
                if (QueueFront(&q))
                {
                    return false;
                }
            }
            return true;
        }
        else
        {
            QueuePush(&q,tmp->pLeft);
            QueuePush(&q, tmp->pRight);
        }
    }
}
//获取一个结点双亲结点
pBTNode GetBinaryTreeNodeParent(pBTNode root,BTDataType x)
{
    pBTNode ret;
    if (root == NULL)
        return NULL;
    if (root->pLeft)
    {
        if (root->pLeft->data == x)
            return root;

    }
    if (root->pRight)
    {
        if (root->pRight->data == x)
            return root;

    }
    ret = GetBinaryTreeNodeParent(root->pLeft, x);
    if (ret)
        return ret;
    ret = GetBinaryTreeNodeParent(root->pRight, x);
    if (ret)
        return ret;
    return NULL;

}
//获取一个结点的左孩子结点
pBTNode GetBinaryTreeNodeLeftChild(pBTNode root, BTDataType x)
{
    pBTNode ret = NULL;

    if (root == NULL)
    {
        return NULL;
    }
    ret = BinaryTreeFind(root,x);
    if (ret->pLeft)
        return ret->pLeft;
}
//获取一个结点的右孩子结点
pBTNode GetBinaryTreeNodeRightChild(pBTNode root, BTDataType x)
{

    pBTNode ret = NULL;

    if (root == NULL)
    {
        return NULL;
    }
    ret = BinaryTreeFind(root, x);
    if (ret->pRight)
        return ret->pRight;
}

//求二叉树的镜像(递归&非递归)
void BinaryTreeMirror(pBTNode root)
{
    if (NULL == root)
        return;
    if (root->pLeft == NULL&&root->pRight == NULL)
        return;
    pBTNode tmp = root->pLeft;
    root->pLeft = root->pRight;
    root->pRight = tmp;

    if (root->pLeft)
        BinaryTreeMirror(root->pLeft);
    if (root->pRight)
        BinaryTreeMirror(root->pRight);
}
//非递归：队列vs栈（即广度与深度交换）
//代码在上篇博客中
//

重点！！！

1、判断一棵树是否是完全二叉树；

我们可以看到，将完全的二叉树的所有结点push到队列里之后，有连续的非NULL结点。中间没有NULL打断。而非完全二叉树非空结点之间右NULL打断。我们可以根据这一区别来判断一棵树是否是完全二叉树。

//判断一棵二叉树树是否是完全二叉树
bool BinaryTreeComplete(pBTNode root)
{

    Queue q;

    if (root == NULL)
        return true;
    QueueInit(&q);

    QueuePush(&q,root);
    while (!QueueEmpty(&q))
    {
        pBTNode tmp = QueueFront(&q);
        QueuePop(&q);
        if (tmp == NULL)
        {
            while (!QueueEmpty(&q))
            {
                QueuePop(&q);
                if (QueueFront(&q))
                {
                    return false;
                }
            }
            return true;
        }
        else
        {
            QueuePush(&q,tmp->pLeft);
            QueuePush(&q, tmp->pRight);
        }
    }
}

2、求二叉树中最远两个结点的距离；
看到这个题，一般大家会有一个思想误区：最远的两个结点是左子树最深结点和右子树最深结点。不是！千万不要这样想！最远结点，即为相距路径最长的两个结点，例如下面两种情况：

最优解法：利用递归（后序递归），划分子问题。
子问题模型：传一个全局变量Max（最远距离），初值设为0，传参类型为传引用。求取当前结点cur左右子树的深度并进行比较，返回较深的子树的深度的值。在返回前，将左右子树的深度相加求的和，与Max进行比较，若和大于Max，将和的值赋给Max。
我们在写代码的时候不要递归到一个结点就对其左右子树求高度。这样会大大增加工作量，降低了程序的效率。采用后序递归，先递归左子树，再递归右子树。将子树高度层层返回，会是最优的解法。令时间复杂度达到O(N)。

参考代码

//求二叉树中最远两个结点的距离
size_t GetMaxLength()
{
    size_t Max = 0;
    MaxLength(root, Max);
    return Max;
}
//求二叉树中最远两个结点的距离
size_t MaxLength(Node* root, size_t &Max)
{
    if (root == NULL)
    {
        return 0;
    }
    if (root->left == NULL && root->right == NULL)
    {
        return 0;
    }
    size_t left = MaxLength(root->left, Max) + 1;//求左子树高度
    size_t right = MaxLength(root->right, Max) + 1;//求右子树高度

    if (Max < left + right)//每次判断Max与left+right的大小
    {
        Max = left + right;
    }
    if (left > right)// 返回左右子树最深的高度
    {
        return left;
    }
    else
    {
        return right;
    }
}

3、由前序和中序遍历序列重建二叉树 （前序序列：1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5）；

想要根据前序和中序遍历序列重建二叉树，首先要知道这两个序列的性质。

• 前序序列：第一个数据为根结点。
• 中序序列：根结点值左侧数据均为左子树，根结点值右侧数据均为右子树。
  
  根绝这个思路，最好的解题方式就是递归。划分子问题。
  子问题模型：由前序找到根结点，由后序取重建这个跟结点的左右子树。

递归求解

//由前序和中序遍历序列重建二叉树 （前序序列：1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5）
void ReCreateTree(const T* prev, const T* In, const int size)
{
    assert(prev);
    assert(In);
    int index = 0;
    root = ReCreatrTree(0, size, size, prev, In, index);
}
//由前序和中序遍历序列重建二叉树 （前序序列：1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5）
//begin end为后序的区间
//size为序列元素的数量
//prev In 分别是指向前序中序序列的指针
//index为下标（前序序列中）
Node* ReCreatrTree(int begin, int end, int size, const T* prev, const T* In, int &index)
{
    if (index < size)
    {
        Node* root = NULL;

        root = new Node(prev[index]);
        int div = 0;
        //前序第一个结点为根节点
        for (int i = begin; i <= end; ++i)
        {
            //在后序中找根节点
            if (In[i] == prev[index])
            {
                div = i;
                break;
            }
        }
        //划分区间 左右两部分
        if (begin <= div - 1)
        {
            root->left = ReCreatrTree(begin, div - 1, size, prev, In, ++index);
        }
        if (div + 1 <= end)
        {
            root->right = ReCreatrTree(div + 1, end, size, prev, In, ++index);
        }

        return root;
    }
    return NULL;
}

4、求二叉树两个结点的最近公共祖先；
求二叉树两个结点的最近公共祖先算是一道常考的面试题。此题只给出了二叉树这个大范围，并没有规定是哪一种二叉树，所以我们可以根据不同的情况给出不同的算法。（到时可以向面试官问清楚这一点，没准儿会加分！）

我们可以将其分为三种情况：

①二叉搜索树（BST:BinarySeachTree）
二叉搜索树是一种比较特殊的情况，所以我们可以根据它的结构特点对它进行“特殊对待”。
二叉搜索树特点：左孩子的值 < 父亲的值 < 右孩子的值。整棵树中没有值重复的结点。
如图为一棵二叉搜索树：

假设现在有两个值，求它们的最近公共祖先。因为是二叉搜索树，没有重复值，所以这两个值肯定一个大，一个小。我们将大的命名为max，小的命名为min。设他们的最近公共祖先叫LastParent。设当前结点为cur
根据二叉搜索树的性质，max，min，cur这三个值肯定满足下面性质中的某一条：
①cur>max >min
说明LastParent在当前结点的左子树中。
②cur< min< max
说明LastParent再当前结点的右子树中。
③min <=cur<=max
说明cur就是LastParent。

例如 ：

利用循环

Node* FindParentBST(Node* child1, Node* child2)
{
    if (_root == NULL)
    {
        return NULL;
    }
    if (child == NULL || child2 == NULL)
    {
        return NULL;
    }
    Node* cur = root;
    while (1)
    {
        //判断当前节点的值是不是在区间内
        if (cur->data >= child1->data && cur->data <= child2->data ||
            cur->data >= child2->data && cur->data <= child1->data)
        {
            return cur;
        }
        //当不在区间内，并且大于其中某一个值，那cur的值一定大于所有值
        //LastParnet在左子树
        else if (cur->data >= child1->data)
        {
            cur = cur->left;
        }
        // 否则在右子树
        else
        {
            cur = cur->right;
        }
    }
}

利用递归

Node* FindParentBST(Node* child1, Node* child2)
{
    if (root == NULL)
    {
        return NULL;
    }
    return __FindParentBST(root, child1, child2);
}
Node* __FindParentBST(Node* root, Node* child1, Node* child2)
{
    if (!root || !child1 || !child2)
    {
        return NULL;
    }
    //当root的值大于两个孩子的最大值时
    if (root->data > max(child1->data, child2->data))
    {
        return __FindParentBST(root->left, child1, child2);
    }
    //当root 的值小于两个孩子的最小值时
    else if (root->data < min(child1->data, child2->data))
    {
        return __FindParentBST(root->right, child1, child2);
    }
    //在区间内，root即为最近公共祖先，返回root
    else
    {
        return root;
    }
}

②有指向父亲结点的指针的“三叉树”

每个节点有三个指针之后接下来看图：



这样，我们就将求最近公共祖先的问题转化成了求两个相交链表的交点的问题。用栈或者计数法都行。归根结底都要统计一下两个单链表结点的长度length1，length2，让长的单链表先走 |length1-length2| 个结点，再让两个链表一起走，直到相遇，相遇点就是交点（最近公共祖先）。

参考代码

//有父亲指针
Node* FindParentH(Node* child1, Node* child2)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (child1&&child2)
    {
        Node* cur1 = child1;
        Node* cur2 = child2;
        size_t sz1 = 0;
        size_t sz2 = 0;
        while (cur1 != root)//计算链表1的长度
        {
            cur1 = cur1->parent;
            sz1++;
        }
        while (cur2 != root)//计算链表2的长度
        {
            cur2 = cur2->parent;
            sz2++;
        }
        cur1 = child1;
        cur2 = child2;
        int n = sz1 - sz2;//求出长度差 让长的先走
        if (sz1 > sz2)
        {
            while (n > 0)
            {
                cur1 = cur1->parent;
                n--;
            }
        }
        else
        {
            n = -n;
            while (n > 0)
            {
                cur2 = cur2->parent;
                n--;
            }
        }
        while (cur1 != cur2)//相遇点即为交点
        {
            cur1 = cur1->parent;
            cur2 = cur2->parent;
        }
        return cur1;
    }
    else
    {
        return NULL;
    }
}

③普通的二叉树，没有指向父亲结点的指针。
如果是普通的二叉树，我们就没有了特殊条件可以利用。只能挨个遍历去找。这里有两种解题方法。
第一种解法：用两个栈
（其实结构类似于栈的都可以如vector，list等。）
现在我们有两个结点，Node1,Node2。用两个栈分别去他们二叉树内的位置，并保存经过的结点。最后做对比找出最近公共祖先结点。

过程如图:

同理，我们得到第二个寻找5的栈，然后对比 。

时间复杂度分析：最坏的情况是二叉树的所有节点都遍历一遍，所以最坏时间复杂度为O(N)。
空间复杂度分析：开辟了两个栈，有空间损耗。最差情况为要找的结点再最深处lgN，开辟了两个栈，空间复杂度为2O(lg
N)，再加上二叉树本身的空间复杂度O(N)，总的空间复杂度为O(N)+2O(lgN)

可以看到，这种方法空间损耗还是比较大的，面试官会要求你写出空间损耗更少的更优算法。看第二种解法。

用两个栈

Node* FindParentS(const T& t1, const T& t2)
{
    if (root == NULL)
    {
        return false;
    }
    //建立两个栈
    stack<Node*> s1;
    stack<Node*> s2;

    Node* cur = root;
    Node* prev = NULL;
    s1.push(cur);
    while (!s1.empty())
    {
        while (cur&& cur->data != t1)
        {
            cur = cur->left;
            if (cur)
            {
                s1.push(cur);
            }
        }
        if (cur&&cur->data == t1)
        {
            break;
        }
        cur = s1.top();
        if (prev == cur)
        {
            s1.pop();
            cur = s1.top();
        }
        prev = cur;
        cur = cur->right;
    }
    if (s1.empty())
    {
        return NULL;
    }
    cur = root;
    prev = NULL;
    s2.push(cur);
    while (!s2.empty())
    {
        while (cur  && cur->data != t2)
        {
            cur = cur->left;
            if (cur)
            {
                s2.push(cur);
            }

        }
        if (cur&&cur->data == t2)
        {
            //s2.push(cur);
            break;
        }
        cur = s2.top();
        if (prev == cur)
        {
            s2.pop();
            cur = s2.top();
        }
        prev = cur;
        cur = cur->right;
    }
    if (s2.empty())
    {
        return NULL;
    }

    int n = s1.size() - s2.size();
    if (s1.size() > s2.size())
    {
        while (n)
        {
            s1.pop();
            n--;
        }
    }
    else
    {
        n = -n;
        while (n)
        {
            s2.pop();
            n--;
        }
    }
    while (s1.top() != s2.top())
    {
        s1.pop();
        s2.pop();
    }
    return s1.top();
}

第二种解法：用递归。
假设我们要找Node1，Node2的最近公共祖先。

递归思想：
①划分成小问题，对每一个节点cur进行左右递归。寻找Node1，Node2。当我们找到一个结点等于这两个值任意一个时，就返回当前节点cur。找不到则返回NULL。
②在cur的左右都寻找完后，会得到两个返回值ret1 （递归cur左子树得到的返回值），ret2（递归cur右子树的到的返回值）。
③如果ret1和ret2都不为空，说明Node1，Node2，一个存在于cur的左子树，一个存在于cur的右子树。cur就是最近公共祖先。
④如果其中一个为空，说明Node1与Node2中只有一个存在于以cur为根节点的二叉树中，返回ret1与ret2中不为空的一个。
⑤如果都为空，则说明Node1，Node2都不存在于以cur为根节点的二叉树中，返回NULL。

如图：

时间复杂度分析：对二叉树所有的结点都遍历了一遍，时间复杂度为O（N）
空间复杂度分析：没有开辟额外的辅助空间，只有建立二叉树与递归的空间占用。空间复杂度为O(N)+O(lgN)

递归

//用递归
//从根节点开始递归，遍历左子树右子树，分解成子问题。当root的左右等于任意某一值时，就返回。
Node* FindParent(const Node* child1, const Node* child2)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (child1&&child2)
    {
        return __FindParent(_root, child1, child2);
    }
    else
    {
        return NULL;
    }
}
Node* __FindParent(Node* root, const Node* child1, const Node* child2)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (root == child1 || root == child2)
    {
        return root;
    }
    //递归左子树
    Node* ret1 = __FindParent(root->left, child1, child2);
    //递归右子树
    Node* ret2 = __FindParent(root->right, child1, child2);
    //当两个返回值都不为空时返回当前结点
    if (ret1&&ret2)
    {
        return root;
    }
    //否则返回不为空的返回值
    else
    {
        Node* ret = (ret1 != NULL ? ret1 : ret2);
        return ret;
    }
}

5、将二叉搜索树转化成有序的双向链表；

对于学过线索二叉树的同学来说，这道题再简单不过了。因为这道题与中序线索化思想相同，更比它简单。
问题分析就不说了，利用前序递归，一遍遍历就搞定。

参考代码

//将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
Node* TreeToList()
{
    if (root == NULL)
    {
        return NULL;
    }

    Node* prev = NULL;
    TreeToList(root, prev);
    Node* cur = root;
    while (cur->left)
    {
        cur = cur->left;
    }
    return cur;
}
bool TreeToList(Node* root, Node*& prev)
{
    static Node* prev = NULL;
    if (root == NULL)
    {
        return false;
    }
    TreeToList(root->left, prev);
    root->left = prev;
    if (prev)
    {
        prev->right = root;
    }
    prev = root;
    TreeToList(root->right, prev);
    return true;
}

结语

今天你学到了多少？欢迎反馈！