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

如何将二叉搜索树转换为双向链表？

二叉搜索树的左子树节点小于当前节点，右子树节点均大于当前节点，二叉搜索树的中序遍历可以得到一个有序序列，问题在于怎么将树的节点转换为链表的节点，由于需要返回有序链表的头结点，因此需要一个head指针记录链表的最左节点，而链表的最左节点就是二叉树的左子树遍历的最左节点，如何判断是否达到二叉树的最左节点呢？这就需要一个pre指针记录前驱节点来判断，pre指针初始化为null，当第一次到达二叉树的最左节点时，pre指针没有被修改过，所以pre==null时就是最左节点，而如果pre!=null，说明当前节点有前驱节点，需要修改前驱节点的右指针为当前节点，当前节点的左指针为前驱节点，并更新pre的值为当前节点，做双向链表的连接操作，再递归进入右子树处理。

参考

参考题解

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    private TreeNode head = null;  // 返回的第一个指针，即最小值，先初始化为null
    private TreeNode pre = null;  // 中序遍历当前值的上一个节点，初值为最小值，先初始化为null
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        // 先递归到最左最小值
        Convert(pRootOfTree.left);
        // 到达最左最小值时，pre还没被修改，初始值为null
        if (pre == null) {
            head = pRootOfTree;  // head指向最左最小值
            pre = pRootOfTree;
        }
        else {  // 非最左最小值的节点做连接操作
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        // 进入右子树递归处理
        Convert(pRootOfTree.right);
        return head;  // return的值没有被上一层处理，仅仅用于最外层的返回
    }
}