二叉搜索树转换双向链表

Problem description

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

Examples

Input:

Output:

Solution

　　采用分治的思想，假设根节点的左右子树已被排成了双向链表，只需要把根节点left指针指向左子树所构成的双向链表末尾节点leftLast（即中序遍历左子树的最后一个节点）。若leftLast非空则leftLast.right = root.
右子树操作类似。找到右子树的中序遍历的第一个节点root .right = rightFirst; 若rightFirst非空则rightFirst.left = root;
此外一个值得注意的问题是Java中的拷贝问题。在记录左右侧中序遍历最后一个节点和第一个节点时。在函数调用后，leftLast仍旧为空。事实上root.left != null..下一篇博文会给出答案。

Code

 public class Solution {
    private TreeNode mLastNode;

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
            left = null;
            right = null;
        }
    }

    public TreeNode convert(TreeNode root) {
        if (root == null) {
            return root;
        }
        mLastNode = null;
        convertNode(root);

        root = mLastNode;
        while (root != null && root.left != null) {
            root = root.left;
        }
        return root;
    }

    private void convertNode(TreeNode root) {

        if (root == null) {
            return;
        }

        if (root.left != null) {
            convertNode(root.left);
        }

        root.left = mLastNode;

        if (mLastNode != null) {
            mLastNode.right = root;
        }

        mLastNode = root;

        if (root.right != null) {
            convertNode(root.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        new Solution().convert(root);
    }
}