《剑指offer》-二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

题目的描述不是很习惯。题目的意思是把二叉树从左到右遍历，相当于双向链表的遍历。

其实就是让二叉树在x方向上的投影点，顺序输出。那么其实就是中序遍历。递归版本如下：

struct TreeNode{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x) :
        val(x), left(NULL), right(NULL){

    }
};

class Solution{
public:
    TreeNode* Convert(TreeNode* root){
        if (root == NULL) return root;
        root = ConvertNode(root);
        while (root->left){
            root = root->left;
        }
        return root;
    }
    TreeNode* ConvertNode(TreeNode* root){
        if (root == NULL) return root;
        if (root->left){
            TreeNode* left = ConvertNode(root->left);  //重要。是递归而不是仅仅取一个节点。
            while (left->right){
                left = left->right;
            }
            left->right = root;
            root->left = left;
        }
        if (root->right){
            TreeNode* right = ConvertNode(root->right);  //重要。是递归而不是仅仅取一个节点。
            while (right->left){
                right = right->left;
            }
            right->left = root;
            root->right = right;
        }
        return root;
    }
};