[劍指offer] 二叉搜尋樹與雙向連結清單

題目描述

輸入一棵二叉搜尋樹，将該二叉搜尋樹轉換成一個排序的雙向連結清單。要求不能建立任何新的結點，隻能調整樹中結點指針的指向。

解題思路

題目可能比較難了解，可以看如下的圖，我們有一棵二叉搜尋樹，要求得右邊的雙向連結清單。

image

在二叉搜尋樹中，左子結點的值總是小于父結點的值，右子節點的值總是大于父結點的值。是以我們在轉換成排序雙向連結清單時，原先指向左子結點的指針調整為連結清單中指向前一個結點的指針，原先指向右子節點的指針調整為連結清單中指向後一個結點的指針。

因為中序周遊是按照從小到大的順序周遊二叉搜尋樹，是以我們用中序周遊樹中的每一個節點得到的正好是要求的排好序的。周遊過程如下：

每次周遊節點的左孩子、右孩子，把左孩子指向轉換連結清單的尾節點，并把末尾指針的右孩子指向自己。右孩子指向節點的右孩子。如果沒有右孩子就傳回。這一過程可以用遞歸實作。

參考代碼

遞歸解法

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    TreeNode head = null;
    TreeNode end = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        ConvertSub(pRootOfTree);
        return head;
    }
    public void ConvertSub(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            return ;
        Convert(pRootOfTree.left);
        if(end == null){
            head = pRootOfTree;
            end = pRootOfTree;
        }else{
            end.right = pRootOfTree;
            pRootOfTree.left = end;
            end = pRootOfTree;
        }
        Convert(pRootOfTree.right);
    }
}
           

非遞歸解法

import java.util.Stack;
public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        TreeNode head = null;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>();
        while(pRootOfTree != null || !stack.isEmpty()){
            while(pRootOfTree != null){
                stack.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }
            pRootOfTree = stack.pop();
            if(head == null){
                head = pRootOfTree;
                pre = pRootOfTree;
            }else{
                pre.right = pRootOfTree;
                pRootOfTree.left = pre;
                pre = pRootOfTree;
            }
            pRootOfTree = pRootOfTree.right;
        }
        return head;
    }
}