剑指offer - 二叉搜索树与双向链表(Java实现)

题目链接：https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路：由于是二叉搜索树，那么在遍历二叉树的时候就可以得到一个升序的序列，然后使用这个序列就可以转换成双向链表。

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

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

}
*/
import java.util.*;

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        ArrayList<TreeNode> list = new ArrayList<>();
        preOrder(list, pRootOfTree);
        return buildTree(list);
    }
    public static TreeNode buildTree(ArrayList<TreeNode> list) { //转换为双向链表
        TreeNode pHead = list.get(0);
        TreeNode cur = pHead;
        for(TreeNode node : list) {
            if(pHead == node) continue;
            node.left = cur;
            cur.right = node;
            cur = node;
        }
        return pHead;
    }
    public static void preOrder(ArrayList<TreeNode> list, TreeNode pRootOfTree) { //前序遍历
        if(pRootOfTree == null) {
            return ;
        }
        preOrder(list, pRootOfTree.left);
        list.add(pRootOfTree);
        preOrder(list, pRootOfTree.right);
    }
}