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

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

• 思路1
  思考点1. 遍历二叉树，对每个节点，将其左节点的右指针指向当前节点，将其右节点的左指针指向当前节点；返回当前节点，为上一级节点的左/右侧子节点。
  思考点2. 返回的节点如果是左子树侧，则将该左子节点一直向右指，找到其最右节点，作为当前节点的左子节点，将该最右节点的右指针指向当前节点（思考点1中的父节点），将当前节点的左指针指向该最右节点；返回的节点如果是右子树侧，则将该右子节点的左指针一直向左指，找到其最左节点，作为当前节点的右子节点，将该最左节点的左指针指向当前节点，将当前节点的右指针指向该最左节点。再返回当前节点，作为上一级节点的左/右侧子节点。如此重复，则可将左右子树拉成链条。
  思考点3. 返回条件：当前节点为空时，返回。

/**
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) {
        if(pRootOfTree == null) return null;
        TreeNode resNode = Convert1(pRootOfTree);
        while(resNode.left != null){
            resNode = resNode.left;
        }
        return resNode;
    }

    public TreeNode Convert1(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;

        //左节点吸上来
        TreeNode leftNode = Convert(pRootOfTree.left);
        //当前是左侧链表的中间位置，把左侧链表的尾结点找到，连接到当前节点上
        while(leftNode!=null && leftNode.right!=null){
            leftNode = leftNode.right;
        }
        if(leftNode!=null) {
            leftNode.right = pRootOfTree;
        }
        pRootOfTree.left = leftNode;
        //右节点为下一层函数的结果
        TreeNode rightNode = Convert(pRootOfTree.right);
        //右侧链表的头结点，接到当前节点上
        while(rightNode!=null && rightNode.left!=null){
            rightNode = rightNode.left;
        }
        if(rightNode!=null){
            rightNode.left = pRootOfTree;
        }
        pRootOfTree.right = rightNode;
        return pRootOfTree;
    }
}

• 思路2
  中序遍历树，用数组将每个节点记录下来，再遍历数组，建立二叉树。

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

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

    }

}
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    ArrayList<treenode> treeNodeList = new ArrayList<treenode>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        //中序遍历二叉树
        Stack<treenode> s = new Stack<treenode>();
        TreeNode curNode = pRootOfTree;
        while(!s.empty() || curNode !=null){
            //左子树压栈
            while(curNode!=null ){
                s.push(curNode);
                curNode = curNode.left;
            }
            //记录节点
            curNode = s.pop();
            treeNodeList.add(curNode);
            //右子树压栈
            curNode = curNode.right;
        }

        TreeNode resNode = treeNodeList.get(0);
        resNode.left = null;
        //建立双向链表
        int i = 0,j = 1;
        for(i = 0,j = 1;j<treenodelist.size();++j,++i){ treenode pre="null;" later="treeNodeList.get(j);" pre.right="later;" later.left="pre;" } treenodelist.get(treenodelist.size()-1).right="null;" return resnode; ``` - 思路3 中序遍历搜索树，节点被遍历的顺序即链表从左到右的顺序，因此，用一个变量记录当前节点pre，当遍历到下一个节点cur时，将pre节点与cur节点建立双向关系，遍历完则链表也建好了。因为是中序遍历，所以链表头结点最先出，最后出的是尾结点，因此，需要用一个res节点记录头结点。 代码采用的是非递归中序遍历（因为我不熟悉非递归遍历，所以多使用该方法，采用递归方法更好理解，主要的连接代码在代码中标注出） ** public class { int val="0;" left="null;" right="null;" treenode(int val) this.val="val;" * import java.util.stack; solution convert(treenode prootoftree) if(prootoftree="=" null) null; 中序遍历二叉树 stack<treenode> s = new Stack<treenode>();
        TreeNode curNode = pRootOfTree;
        TreeNode resNode = null;
        while(!s.empty() || curNode !=null){
            //左子树压栈
            while(curNode!=null ){
                s.push(curNode);
                curNode = curNode.left;
            }
            ///连接代码 begin
            //记录节点
            curNode = s.pop();
            if(pre!= null){
                pre.right = curNode;
                curNode.left = pre;
            }
            else{
                resNode = curNode;
            }
            pre = curNode;
            ///连接代码 end
            //右子树压栈
            curNode = curNode.right;
        }

        return resNode;
    }

}

• 思路4
  与思路3相同，只是遍历顺序改用反向中序遍历（右-根-左），这样，链表头节点最后出，就无需使用一个res变量来记录头结点了。

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

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

    }
}
*/
import java.util.Stack;
public class Solution {
   TreeNode pre = null;
    boolean isFirst = true;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        Convert(pRootOfTree.right);
        if(pre!=null){
            pre.left = pRootOfTree;
            pRootOfTree.right = pre;
        }
        pre = pRootOfTree;
        if(isFirst){
            pre.right = null;
            isFirst = false;
        }
        Convert(pRootOfTree.left);
        return pre;
    }
}