不需要额外空间,中序遍历,修改指针即可。
public class Solution { public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null || (pRootOfTree.left==null && pRootOfTree.right==null)) return pRootOfTree; return convert(pRootOfTree, false); } private static TreeNode convert(TreeNode node, boolean is_left) { if(node==null) return null; node.left = convert(node.left, true); //使用左子树递归,返回的是左子树最右边的结点 if(node.left!=null) node.left.right = node; node.right = convert(node.right, false); //使用右子树递归,返回的是右子树最左边的结点 if(node.right!=null) node.right.left = node; // 如果是左子树,则返回最右侧结点 while(is_left && (node.right!=null)) node = node.right; //如果是右子树,则返回最左侧结点 while((!is_left)&& (node.left!=null)) node = node.left; return node; } }