二叉搜索樹與雙向鏈表

OJ鏈接

二叉樹搜索樹與雙向鏈表

描述

輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。如下圖所示

數(shù)據(jù)范圍：輸入二叉樹的節(jié)點(diǎn)數(shù)0 \le n \le 10000≤n≤1000，二叉樹中每個節(jié)點(diǎn)的值0\le val \le 10000≤val≤1000

要求：空間復(fù)雜度O(1)O(1)（即在原樹上操作），時間復(fù)雜度O(n)O(n)

注意:

1.要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。當(dāng)轉(zhuǎn)化完成以后，樹中節(jié)點(diǎn)的左指針需要指向前驅(qū)，樹中節(jié)點(diǎn)的右指針需要指向后繼

2.返回鏈表中的第一個節(jié)點(diǎn)的指針

3.函數(shù)返回的TreeNode，有左右指針，其實可以看成一個雙向鏈表的數(shù)據(jù)結(jié)構(gòu)

4.你不用輸出雙向鏈表，程序會根據(jù)你的返回值自動打印輸出

知識點(diǎn)-二叉樹遞歸

遞歸是一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解。因此遞歸過程，最重要的就是查看能不能講原本的問題分解為更小的子問題，這是使用遞歸的關(guān)鍵。

而二叉樹的遞歸，則是將某個節(jié)點(diǎn)的左子樹、右子樹看成一顆完整的樹，那么對于子樹的訪問或者操作就是對于原樹的訪問或者操作的子問題，因此可以自我調(diào)用函數(shù)不斷進(jìn)入子樹。

知識點(diǎn)-二叉搜索樹

二叉搜索樹是一種特殊的二叉樹，它的每個節(jié)點(diǎn)值大于它的左子節(jié)點(diǎn)，且大于全部左子樹的節(jié)點(diǎn)值，小于它右子節(jié)點(diǎn)，且小于全部右子樹的節(jié)點(diǎn)值。因此二叉搜索樹一定程度上算是一種排序結(jié)構(gòu)。

思路

二叉搜索樹最左端的元素一定最小，最右端的元素一定最大，符合“左中右”的特性，因此二叉搜索樹的中序遍歷就是一個遞增序列，我們只要對它中序遍歷就可以組裝稱為遞增雙向鏈表。

具體做法

定義兩個指針pCur和prev, pCur的當(dāng)前節(jié)點(diǎn)的指針, prev是pCur的前驅(qū)節(jié)點(diǎn)的指針, 因此只要pre不為空, 連接方案就是prev.right = pCur, pCur.left = prev

二叉樹中序遍歷的順序是左兒子->根節(jié)點(diǎn)->右兒子, 故我們只要按中序遍歷的順序移動prev和pCur指針, 就可以將整個二叉樹連接為一條雙向鏈表

代碼

/**
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 pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }  
        TreeNode head = pRootOfTree;      
        convertChild(pRootOfTree);
        while(head.left!=null){
            head = head.left;
        }
        return head;
    }
    TreeNode prev = null;
    //pCur為當(dāng)前節(jié)點(diǎn)
    private void convertChild(TreeNode pCur){
        //遞歸出口
        if(pCur == null){
            return ;
        }
        //中序遍歷，先找到最左邊的節(jié)點(diǎn)，并與prev建立連接
        convertChild(pCur.left);
        pCur.left = prev;
        if(prev != null){
            prev.right = pCur;
        }
        //prev更新
        prev = pCur;
        convertChild(pCur.right);
    }
}

到此這篇關(guān)于Java實題演練二叉搜索樹與雙向鏈表分析的文章就介紹到這了,更多相關(guān)Java二叉搜索樹與雙向鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論