思路

使用分治思想，将大问题分割成一个个相同的小问题，创建一个递归方法，对传入的树进行双向链表化，使用二叉树的中序遍历遍历整个树的同时调用方法进行转换 注意递归方法的分情况讨论：

1. 当传入节点为n0时，我们应当无任何操作
2. 当传入节点为n1时，说明该节点不存在左子节点或者右子节点，我们只需要进行默认变换即可
3. 如果传入节点为n2，说明该节点左右子树都存在，我们应当对其上一层调用返回该节点。

对于变换应当分默认变换与特殊变换：

• 默认变换：让当前节点的左子节点的后继指向当前节点(如果有的话)，当前节点的右子节点的前驱指向当前节点
• 特殊变换：因为返回值有左子节点或者右子节点，表明该节点为n2，需要分情况进行连接：
  1. 如果是左子节点，则左子节点的右子节点的后继应当指向当前节点，当前节点的前驱应当指向左子节点的右子节点
  2. 如果是右子节点，则右子节点的左子节点的前驱应当指向当前节点，当前节点的后继应当指向右子节点的左子节点

代码

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

    /**
     * 将传入的树转换成双向链表
     *
     * @param root 根节点
     * @return TreeNode
     * @apiNote
     * @since 2022/12/31 17:18
     */
    public TreeNode transform(TreeNode root) {
        if (root != null) {
            if (root.left != null) {
                // 返回值为左子节点
                TreeNode transform = transform(root.left);
                // 如果返回的节点不为空且该节点存在右子节点才符合条件，否则该节点度为1
                if (transform != null && transform.right != null) {
                    // 让该节点的右子节点的后继指向当前根节点
                    transform.right.right = root;
                    // 让当前根节点的前驱指向该节点的右子节点
                    root.left = transform.right;
                } else {
                    // 将左子树的右驱指向根节点(根节点左驱已经指向了左子节点)
                    root.left.right = root;
                }
            }
            // 递归的调用转换方法传入右子树
            if (root.right != null) {
                // 返回值为右子节点
                TreeNode transform = transform(root.right);
                // 如果返回的节点不为空且该节点存在左子节点才符合条件，否则该节点度为1
                if (transform != null && transform.left != null) {
                    // 让该节点的左子节点的前驱指向当前根节点
                    transform.left.left = root;
                    // 让当前根节点的后继指向该节点的左子节点
                    root.right = transform.left;
                } else {
                    // 将右子树的左驱指向根节点(根节点右驱已经指向了右子节点)
                    root.right.left = root;
                }
            }
            // 当前节点为叶子节点，返回null
            if (root.right == null && root.left == null) {
                return null;
            }
            // 返回当前节点
            return root;
        }
        return null;
    }
}