二叉树转链表

题目如截图所示：

图片.png

如图可知，每执行一步，都要将当前节点的左子树插入到当前节点和当前节点的右节点之间，如果不存在左子树，则指针指向右节点，所以可使用如下递归方式：

private static void treeToLinkedList(TreeNode node) {
    if (node == null) return;
    if (node.left != null) {
        TreeNode left = node.left;
        // 获取当前节点的前驱节点
        TreeNode preNode = getPreNode(node);
        preNode.right = node.right;
        node.right = node.left;
        node.left = null;
        treeTolinkedList(left);
    } else {
        treeTolinkedList(node.right);
    }
}
    
private static TreeNode getPreNode(TreeNode node) {
    TreeNode pre = node.left;
    while (pre.right != null) {
        pre = pre.right;
    }
    return pre;
}

有没有更精简的实现方式呢？下边的某位大牛的代码思想：

private static void treeTolinkList2(TreeNode root) {
    treeTolinkList2(root, null);
}
    
private static TreeNode treeTolinkList2(TreeNode node, TreeNode right) {
    if (node == null) return right;
    node.right = treeTolinkList2(node.left, treeTolinkList2(node.right, right));
    node.left = null;
    return node;
}

代码的思想和我的一致，每次遍历均将左节点接入到当前节点的右节点之上，如果不存在左节点了，便直接接入当前节点的右节点，并将左节点置为null。
以下是我的测试用例：

public static void main(String[] args) {
    TreeNode node16 = new TreeNode(16);
    TreeNode node18 = new TreeNode(18);
    TreeNode node19 = new TreeNode(19, node18, null);
    TreeNode node17 = new TreeNode(17);
    TreeNode node23 = new TreeNode(23);
    TreeNode node22 = new TreeNode(22, node17, node23);
    TreeNode node21 = new TreeNode(21, node16, node19);
    TreeNode node20 = new TreeNode(20, node21, node22);
        
//      treeTolinkedList1(node20);
    treeTolinkList2(node20);
    TreeNode cur = node20;
    while(cur != null) {
        System.out.println(cur.value);
        cur = cur.right;
    }
}

平时在练习过程中，随着练习的增多，代码也随之增大，删之可惜，本文所写纯粹是为记录点滴的需要，如有雷同纯属巧合。