《劍指offer》-将二叉搜尋樹轉化為雙向連結清單

/*
 * 輸入一棵二叉搜尋樹，将該二叉搜尋樹轉換成一個排序的雙向連結清單。
 * 要求不能建立任何新的結點，隻能調整樹中結點指針的指向。
 */
public class ConvertBinaryTreeToDoublyLinkedList {
	public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null || 
          (pRootOfTree.left == null && pRootOfTree.right == null)) {
        	return pRootOfTree;
        }
        
        //拿到左子樹(展開成連結清單的形式)的頭節點,并找到左子樹的末尾節點
        TreeNode left = Convert(pRootOfTree.left);
        TreeNode p = left;
        while(p != null && p.right != null) {
        	p = p.right;
        }  
        //将根節點接上左子樹的末尾節點
        if(p != null) {
        	p.right = pRootOfTree;
        	pRootOfTree.left = p;
        }
        
        //拿到右子樹的頭節點
        TreeNode right = Convert(pRootOfTree.right);
        //将根節點接上右子樹的頭節點
        if(right != null) {
        	pRootOfTree.right = right;
        	right.left = pRootOfTree;
        }
        
        return left == null ? pRootOfTree : left;
    }
	
	//改進法二：左子樹最後一個葉子節點必為左子樹的末尾節點,可以省去周遊左子樹的末尾節點
	TreeNode leftLast = null;
	public TreeNode Convert2(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
        	return pRootOfTree;
        }
        
        if(pRootOfTree.left == null && pRootOfTree.right == null) {
        	leftLast = pRootOfTree;
        	return pRootOfTree;
        }
        
        //拿到左子樹的頭節點,并将根節點接上左子樹的末尾節點
        TreeNode left = Convert2(pRootOfTree.left);
        if(left != null && leftLast != null) {
        	leftLast.right = pRootOfTree;
        	pRootOfTree.left = leftLast;
        }
        
        //拿到右子樹的頭節點
        TreeNode right = Convert2(pRootOfTree.right);
        //将根節點接上右子樹的頭節點
        if(right != null) {
        	pRootOfTree.right = right;
        	right.left = pRootOfTree;
        }
        
        return left == null ? pRootOfTree : left;
    }

	public static void main(String[] args) {
		TreeNode root1 = new TreeNode(1);
		root1.left = new TreeNode(2);
		root1.right = new TreeNode(3);
		root1.left.left = new TreeNode(4);
		root1.left.right = new TreeNode(5);
		root1.right.left = new TreeNode(6);
		root1.right.right = new TreeNode(7);
		
		TreeNode node = new ConvertBinaryTreeToDoublyLinkedList().Convert2(root1);
		while(node != null) {
			System.out.print(node.val + " ");
			node = node.right;
		}
	}
}