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 { public TreeNode Convert(TreeNode pRootOfTree) { if (pRootOfTree == null) return null; TreeNode[] res = convert(pRootOfTree); return res[0]; } public TreeNode[] convert(TreeNode root) { //TreeNode[0]是转换链表的最左侧节点 //TreeNode[1]是转换链表的最右侧节点 if (root.left == null && root.right == null) return new TreeNode[] {root, root}; TreeNode[] leftRes = new TreeNode[2]; TreeNode[] rightRes = new TreeNode[2]; TreeNode[] curRes = new TreeNode[2]; if (root.left != null) { leftRes = convert(root.left); //拼接 leftRes[1].right = root; root.left = leftRes[1]; curRes[0] = leftRes[0]; } else { curRes[0] = root; } if (root.right != null) { rightRes = convert(root.right); //拼接 rightRes[0].left = root; root.right = rightRes[0]; curRes[1] = rightRes[1]; } else { curRes[1] = root; } return curRes; } }