輸入1棵2叉搜索樹，將該2叉搜索樹轉換成1個排序的雙向鏈表。要求不能創建任何新的結點，只能調劑樹中結點指針的指向。
根據上圖可以發現是中序遍歷的進程
但是我們需要改變其結點關系
中序遍歷：左根右
調劑后:
root.left = ListLeft
ListLeft.right = root
root.right = ListRight
ListRight.left = root
下面程序為了返回值就是頭節點，所有先遍歷右子樹，后調劑結點，最后遍歷左子樹。
public class Solution {
TreeNode list = null;
public TreeNode Convert(TreeNode pNode){
if(pNode ==null)
return pNode;
TreeNode pCur = pNode;
if(pCur.right!=null)
Convert(pCur.right);
pCur.right = list;
if(list!=null)
list.left = pCur;
list = pCur;
if(pCur.left!=null)
Convert(pCur.left);
return list;
}
}討論中左根右遞歸程序
/**
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 root) {
if(root==null)
return null;
if(root.left==null&&root.right==null)
return root;
TreeNode left=Convert(root.left);// 最左結點，頭結點
TreeNode tmpLeft=left; // 找到最右結點
while(tmpLeft!=null&&tmpLeft.right!=null){
tmpLeft=tmpLeft.right;
}
if(left!=null){// 調劑
tmpLeft.right=root;
root.left=tmpLeft;
}
TreeNode right=Convert(root.right);
if(right!=null){
root.right=right;
right.left=root;
}
return left!=null?left:root;
}
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
