1 通过递归的写法,中序遍历二叉搜索树,递归函数返回的是中序遍历当前的子树后形成的链表的最后一个节点,所以需要在递归函数完成后,通过while循环找到头节点。
2 在递归函数中第一个引用指向当前节点,第二个引用指向中序遍历的上一个节点,通过修改两个节点的指向即可完成链表的一个节点的构建
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null)
{
return null;
}
else {
TreeNode lastNode=null;
lastNode=Convert(pRootOfTree,lastNode);
while(lastNode!=null&&lastNode.left!=null)
{
lastNode=lastNode.left;
}
return lastNode;
} } public TreeNode Convert(TreeNode pRootOfTree,TreeNode lastNode) { if(pRootOfTree==null) { return null; } TreeNode cruent=pRootOfTree; if(pRootOfTree.left!=null) lastNode=Convert(pRootOfTree.left,lastNode); if(lastNode!=null) lastNode.right=cruent; cruent.left= lastNode; lastNode=cruent; if(pRootOfTree.right!=null) lastNode=Convert(pRootOfTree.right,lastNode); return lastNode; }