题解 | #二叉搜索树与双向链表#

第二十题 中序遍历 修改左右子树的链为双向链表 

是十二题的复杂版本 只写了递归的版本  非递归太复杂了

递归调用的中序遍历

利用preNode保存着前一项

当访问下一个结点的时候，更新 preNode的right和当前结点的left

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    // 保存前一个结点 在不同函数之间使用 要全局变量
    TreeNode* preNode;
    TreeNode* Convert(TreeNode* pRootOfTree) {
        // 原先就是中序遍历 创建双向链表
        // 但要求是不能创建新结点 只能在二叉树上修改
        // 所以在之前对于之前preNode要保存下来
        // 递归调用
        if(pRootOfTree == NULL)
            return pRootOfTree;
        
        TreeNode * ret_ans=pRootOfTree;
        // 返回的头结点 永远是最左下的那个点
        while(ret_ans->left!=NULL)
            ret_ans = ret_ans->left;
        
        // 中序遍历 递归调用
        zhongxvbianli(pRootOfTree);
        return ret_ans;

    }
    void zhongxvbianli(TreeNode* root){
        if(root ==NULL)
            return;
        
        // 中序遍历 左根右
        // 左子树先遍历 不然左边结点被修改了 就找不到了
        zhongxvbianli(root->left);
        
        // 根 修改left 和 right
        // 左边指向 前一个结点 前一个结点的右边 指向当前结点 4指向6；6指向4
        root->left=preNode;
        if(preNode!=NULL)
            preNode->right=root;
        preNode=root;
        
        // 右子树遍历
        zhongxvbianli(root->right);
        
    }
};