二叉搜索樹與雙向鏈表

OJ鏈接

二叉樹搜索樹與雙向鏈表

描述

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

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

要求：空間復(fù)雜度O(1)O(1)（即在原樹上操作），時(shí)間復(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.返回鏈表中的第一個(gè)節(jié)點(diǎn)的指針

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

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

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

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

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

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

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

思路

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

具體做法

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

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

代碼

/**
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實(shí)題演練二叉搜索樹與雙向鏈表分析的文章就介紹到這了,更多相關(guān)Java二叉搜索樹與雙向鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！