C语言解题思路

1. 思路：二叉树一般想到递归解决问题，分左右子树考虑，从二叉树到链表的过程可以看到，以根节点为中心，左子树看作一个整体，左子树的后继节点为根节点，右子树的前驱节点为根节点，使用递归解决问题
2. 递归出口：二叉树最小子树分两种情况，一种是有两个叶子，一种是只有一个叶子。因此需要给两个出口，对于两个叶子的最小子树，出口可以根据叶子左右孩子为空判断；对于一个叶子节点的最小子树，出口应包含一个本身是否为空。对最小子树需要对其左孩子，右孩子递归，孩子为空则返回
3. 重点：考虑双向链表的特性，两条链，从最左可以得到最有，从最右也可以得到最左。在递归时，先从最小子树分析，完成指针移动后，统一返回最左侧节点
4. 不严谨之处：本道题只能返回最左侧节点

 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pRootOfTree TreeNode类 
 * @return TreeNode类
 */
struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
    //递归的一个出口 空节点返回空
    if(pRootOfTree==NULL)
        return NULL;
    //常规叶子节点，直接返回这个叶子节点
    if(pRootOfTree->left==NULL && pRootOfTree->right==NULL)
        return pRootOfTree;
    //递归得到左孩子返回值
    struct TreeNode* lchild= Convert(pRootOfTree->left);
    //左子树返回非空 找到左子树的最右侧节点
    if(lchild!=NULL){
        while(lchild->right)
            lchild=lchild->right;
        //变双向链表
        lchild->right=pRootOfTree;
        pRootOfTree->left=lchild;
    }
    
    //右子树返回值 变双向链表
    struct TreeNode* rchild=Convert(pRootOfTree->right);
    if(rchild!=NULL){
        rchild->left=pRootOfTree;
        pRootOfTree->right=rchild;
    }
    struct TreeNode* temp=pRootOfTree;
    //每次返回最双向链表右侧的节点
    while(temp->left)
        temp=temp->left;
    return temp;
    
}