剑指offer（26）将二叉排序树转化成双向链表

之前一直没看懂这个题，今天才看懂

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {//这个方法里是双向链表←的过程
        TreeNode last = ConvertNode(pRootOfTree , null);//用一个last的指针来指向遍历到的最后一个节点
        while(last != null && last.left != null){//一直想左，双向链表最左的节点为last
            last = last.left;
        }
        return last;
    }
    public TreeNode ConvertNode(TreeNode root, TreeNode last){//这个方法是双向链表遍历→的过程
        if(root == null){
            return null;
        }
        if(root.left != null){//root的左子树的最后一个节点为last
            last = ConvertNode(root.left , last);
        }
       root.left = last;//左子树的最左节点为last
        if(last != null){//说明左子树的改的链表是存在的，则将root接到左子树的最后一个节点后面
            last.right = root;
        }
        last = root;//这个时候last节点变为root了
        if(root.right != null){//继续遍历右子树
            last = ConvertNode(root.right , last);
        }
        return last;//双向链表向→的最后一个节点
    }
}