国产一区二区999,2020国产精品

前言

二叉樹的前序遍歷，中序遍歷，后序遍歷是面試中常?？疾斓幕舅惴?，關(guān)于它的概念這里不再贅述了，還不了解的同學(xué)可以去翻翻LeetCode的解釋。

這里，我個(gè)人對這三個(gè)遍歷順序理解是：前 中 后 這三個(gè)詞是針對根節(jié)點(diǎn)的訪問順序而言的，即前序就是根節(jié)點(diǎn)在最前根->左->右，中序是根節(jié)點(diǎn)在中間左->根->右，后序是根節(jié)點(diǎn)在最后左->右->根。

無論哪種遍歷順序，用遞歸總是最容易實(shí)現(xiàn)的，也是最沒有含金量的。但我們至少要保證能信手捏來地把遞歸寫出來，在此基礎(chǔ)上，再掌握非遞歸的方式。

在二叉樹的順序遍歷中，常常會(huì)發(fā)生先遇到的節(jié)點(diǎn)到后面再訪問的情況，這和先進(jìn)后出的棧的結(jié)構(gòu)很相似，因此在非遞歸的實(shí)現(xiàn)方法中，我們最常使用的數(shù)據(jù)結(jié)構(gòu)就是棧。

前序遍歷

前序遍歷（題目見這里）是三種遍歷順序中最簡單的一種，因?yàn)?code>根節(jié)點(diǎn)是最先訪問的，而我們在訪問一個(gè)樹的時(shí)候最先遇到的就是根節(jié)點(diǎn)。

遞歸法

遞歸的方法很容易實(shí)現(xiàn)，也很容易理解：我們先訪問根節(jié)點(diǎn)，然后遞歸訪問左子樹，再遞歸訪問右子樹，即實(shí)現(xiàn)了根->左->右的訪問順序，因?yàn)槭褂玫氖沁f歸方法，所以每一個(gè)子樹都實(shí)現(xiàn)了這樣的順序。

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        result.add(root.val); // 訪問根節(jié)點(diǎn)
        preorderHelper(root.left, result); // 遞歸遍歷左子樹
        preorderHelper(root.right, result); //遞歸遍歷右子樹
    }
}

迭代法

在迭代法中，我們使用棧來實(shí)現(xiàn)。由于出棧順序和入棧順序相反，所以每次添加節(jié)點(diǎn)的時(shí)候先添加右節(jié)點(diǎn)，再添加左節(jié)點(diǎn)。這樣在下一輪訪問子樹的時(shí)候，就會(huì)先訪問左子樹，再訪問右子樹：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) return result;

        Stack<TreeNode> toVisit = new Stack<>();
        toVisit.push(root);
        TreeNode cur;

        while (!toVisit.isEmpty()) {
            cur = toVisit.pop();
            result.add(cur.val); // 訪問根節(jié)點(diǎn)
            if (cur.right != null) toVisit.push(cur.right); // 右節(jié)點(diǎn)入棧
            if (cur.left != null) toVisit.push(cur.left); // 左節(jié)點(diǎn)入棧
        }
        return result;
    }
}

中序遍歷

中序遍歷（題目見這里）相對前序遍歷要復(fù)雜一點(diǎn)，因?yàn)槲覀冋f過，在二叉樹的訪問中，最先遇到的是根節(jié)點(diǎn)，但是在中序遍歷中，最先訪問的不是根節(jié)點(diǎn)，而是左節(jié)點(diǎn)。（當(dāng)然，這里說復(fù)雜是針對非遞歸方法而言的，遞歸方法都是很簡單的。）

遞歸法

無論對于哪種方式，遞歸的方法總是很容易實(shí)現(xiàn)的，也是很符合直覺的。對于中序遍歷，就是先訪問左子樹，再訪問根節(jié)點(diǎn)，再訪問右子樹，即 左->根->右：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        inorderHelper(root, result);
        return result;
    }

    private void inorderHelper(TreeNode root, List<Integer> result) {
        if(root == null) return;
        inorderHelper(root.left, result); // 遞歸遍歷左子樹
        result.add(root.val); // 訪問根節(jié)點(diǎn)
        inorderHelper(root.right, result); // 遞歸遍歷右子樹
    }
}

大家可以對比它和前序遍歷的遞歸實(shí)現(xiàn)，二者僅僅是在節(jié)點(diǎn)的訪問順序上有差別，代碼框架完全一致。

迭代法

中序遍歷的迭代法要稍微復(fù)雜一點(diǎn)，因?yàn)樽钕扔龅降母?jié)點(diǎn)不是最先訪問的，我們需要先訪問左子樹，再回退到根節(jié)點(diǎn)，再訪問根節(jié)點(diǎn)的右子樹，這里的一個(gè)難點(diǎn)是從左子樹回退到根節(jié)點(diǎn)的操作，雖然可以用棧來實(shí)現(xiàn)回退，但是要注意在出棧時(shí)保存根節(jié)點(diǎn)的引用，因?yàn)槲覀冞€需要通過根節(jié)點(diǎn)來訪問右子樹：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> toVisit = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !toVisit.isEmpty()) {
            while (cur != null) {
                toVisit.push(cur); // 添加根節(jié)點(diǎn)
                cur = cur.left; // 循環(huán)添加左節(jié)點(diǎn)
            }
            cur = toVisit.pop(); // 當(dāng)前棧頂已經(jīng)是最底層的左節(jié)點(diǎn)了，取出棧頂元素，訪問該節(jié)點(diǎn)
            result.add(cur.val);
            cur = cur.right; // 添加右節(jié)點(diǎn)
        }
        return result;
    }
}

這里：

while (cur != null) {
    toVisit.push(cur); 
    cur = cur.left; 
}

↑這一部分實(shí)現(xiàn)了遞歸添加左節(jié)點(diǎn)的作用。

cur = toVisit.pop();
result.add(cur.val);
cur = cur.right;

↑這一部分實(shí)現(xiàn)了對根節(jié)點(diǎn)的遍歷，同時(shí)將指針指向了右子樹，在下輪中遍歷右子樹。

在看這部分代碼中，腦海中要有一個(gè)概念：當(dāng)前樹的根節(jié)點(diǎn)的左節(jié)點(diǎn)，是它的左子樹的根節(jié)點(diǎn)。因此從不同的層次上看，左節(jié)點(diǎn)也是根節(jié)點(diǎn)。另外，LeetCode上也提供了關(guān)于中序遍歷的動(dòng)態(tài)圖的演示，感興趣的讀者可以去看一看。

后序遍歷

后序遍歷（題目見這里）是三種遍歷方法中最難的，與中序遍歷相比，雖然都是先訪問左子樹，但是在回退到根節(jié)點(diǎn)的時(shí)候，后序遍歷不會(huì)立即訪問根節(jié)點(diǎn)，而是先訪問根節(jié)點(diǎn)的右子樹，這里要小心的處理入棧出棧的順序。（當(dāng)然，這里說復(fù)雜是針對非遞歸方法而言的，遞歸方法都是很簡單的。）

遞歸法

無論對于哪種方式，遞歸的方法總是很容易實(shí)現(xiàn)的，也是很符合直覺的。對于后序遍歷，就是先訪問左子樹，再訪問右子樹，再訪問根節(jié)點(diǎn)，即 左->右->根：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        postorderHelper(root, result);
        return result;
    }

    private void postorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        postorderHelper(root.left, result); // 遍歷左子樹
        postorderHelper(root.right, result); // 遍歷右子樹
        result.add(root.val); // 訪問根節(jié)點(diǎn)
    }
}

與前序遍歷和后序遍歷相比，代碼結(jié)構(gòu)完全一致，差別僅僅是遞歸函數(shù)的調(diào)用順序。

迭代法

前面說過，與中序遍歷不同的是，后序遍歷在訪問完左子樹向上回退到根節(jié)點(diǎn)的時(shí)候不是立馬訪問根節(jié)點(diǎn)的，而是得先去訪問右子樹，訪問完右子樹后在回退到根節(jié)點(diǎn)，因此，在迭代過程中要復(fù)雜一點(diǎn)：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> toVisit = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null;

        while (cur != null || !toVisit.isEmpty()) {
            while (cur != null) {
                toVisit.push(cur); // 添加根節(jié)點(diǎn)
                cur = cur.left; // 遞歸添加左節(jié)點(diǎn)
            }
            cur = toVisit.peek(); // 已經(jīng)訪問到最左的節(jié)點(diǎn)了
            //在不存在右節(jié)點(diǎn)或者右節(jié)點(diǎn)已經(jīng)訪問過的情況下，訪問根節(jié)點(diǎn)
            if (cur.right == null || cur.right == pre) { 
                toVisit.pop();
                result.add(cur.val);
                pre = cur;
                cur = null;
            } else {
                cur = cur.right; // 右節(jié)點(diǎn)還沒有訪問過就先訪問右節(jié)點(diǎn)
            }
        }
        return result;
    }
}

這里尤其注意后續(xù)遍歷和中序遍歷中對于從最左側(cè)節(jié)點(diǎn)向上回退時(shí)的處理：

image.png

在后序遍歷中，我們首先使用的是：

cur = toVisit.peek();

注意，這里使用的是peek而不是pop，這是因?yàn)槲覀冃枰紫热ピL問右節(jié)點(diǎn)，下面的：

if (cur.right == null || cur.right == pre)

就是用來判斷是否存在右節(jié)點(diǎn)，或者右節(jié)點(diǎn)是否已經(jīng)訪問過了，如果右節(jié)點(diǎn)已經(jīng)訪問過了，則接下來的操作就和中序遍歷的情況差不多了，所不同的是，這里多了兩步：

pre = cur;
cur = null;

這兩步的目的都是為了在下一輪遍歷中不再訪問自己，cur = null很好理解，因?yàn)槲覀儽仨氃谝惠喗Y(jié)束后改變cur的值，以添加下一個(gè)節(jié)點(diǎn)，所以它和cur = cur.right一樣，目的都是指向下一個(gè)待遍歷的節(jié)點(diǎn)，只是在這里，右節(jié)點(diǎn)已經(jīng)訪問過了，則以當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)的整個(gè)子樹都已經(jīng)訪問過了，接下來應(yīng)該回退到當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，而當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)已經(jīng)在棧里了，所以我們并沒有新的節(jié)點(diǎn)要添加，直接將cur設(shè)為null即可。

pre = cur 的目的有點(diǎn)類似于將當(dāng)前節(jié)點(diǎn)標(biāo)記為已訪問，它是和if條件中的cur.right == pre配合使用的。注意這里的兩個(gè)cur指的不是同一個(gè)節(jié)點(diǎn)。我們假設(shè)當(dāng)前節(jié)點(diǎn)為C，當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為A，而C是A的右孩子，則當(dāng)前cur是C，但在一輪中，cur將變成A，則：

         A 
        / \
       B   C (pre)

pre = cur 就是 pre = C
if (cur.right == null || cur.right == pre) 就是 if (A.right == null || A.right == pre)

這里，由于A是有右節(jié)點(diǎn)的，它的右節(jié)點(diǎn)就是C，所以A.right == null不成立。但是C節(jié)點(diǎn)我們在上一輪已經(jīng)訪問過了，所以這里為了防止進(jìn)入else語句重復(fù)添加節(jié)點(diǎn)，我們多加了一個(gè)A.right == pre條件，它表示A的右節(jié)點(diǎn)已經(jīng)訪問過了，我們得以進(jìn)入if語句內(nèi)，直接訪問A節(jié)點(diǎn)。

雙棧法

前面我們說過，前序遍歷之所以最簡單，是因?yàn)楸闅v過程中最先遇到的根節(jié)點(diǎn)是最先訪問的，而在后序遍歷中，最先遇到的根節(jié)點(diǎn)是最后訪問的，所以導(dǎo)致了上面的迭代法非常復(fù)雜，那有沒有辦法簡化一下呢？其實(shí)是有的。

大家仔細(xì)觀察一下后序遍歷的順序左->右->根，根節(jié)點(diǎn)在最后，要是能像前序遍歷一樣把它放在最前面就好了，怎么辦呢？一個(gè)最簡單的方法就是倒個(gè)序，即將左->右->根倒序成根->右->左，這樣不就和前序遍歷的根->左->右差不多了嗎？而因?yàn)闂１旧砭褪呛筮M(jìn)先出的，是天然的倒序工具，因此，我們只需要再用一個(gè)棧將輸出順序反過來即可，由此，雙棧法應(yīng)運(yùn)而生，它的思路是：

用一個(gè)棧實(shí)現(xiàn) 根->右->左 的遍歷
用另一個(gè)棧將遍歷順序反過來，使之變成 左->右->根

下面我們來看實(shí)現(xiàn)：

首先，在最開始的前序遍歷中，我們已經(jīng)實(shí)現(xiàn)了遞歸方式的根->左->右的遍歷，如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) return result;

        Stack<TreeNode> toVisit = new Stack<>();
        toVisit.push(root);
        TreeNode cur;

        while (!toVisit.isEmpty()) {
            cur = toVisit.pop();
            result.add(cur.val); // 訪問根節(jié)點(diǎn)
            if (cur.right != null) toVisit.push(cur.right); // 右節(jié)點(diǎn)入棧
            if (cur.left != null) toVisit.push(cur.left); // 左節(jié)點(diǎn)入棧
        }
        return result;
    }
}

那么要實(shí)現(xiàn)根->右->左的遍歷，只需要交換左右節(jié)點(diǎn)的入棧順序即可，即：
（代碼中將與前序遍歷相同的代碼部分注釋起來了，好讓大家能直觀地看到不同點(diǎn)，下同）

//class Solution {
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> result = new LinkedList<>();
//        if (root == null) return result;
//
//        Stack<TreeNode> toVisit = new Stack<>();
//        toVisit.push(root);
//        TreeNode cur;
//
//        while (!toVisit.isEmpty()) {
//            cur = toVisit.pop();
//            result.add(cur.val); // 訪問根節(jié)點(diǎn)
              if (cur.left != null) toVisit.push(cur.left); // 左節(jié)點(diǎn)入棧
              if (cur.right != null) toVisit.push(cur.right); // 右節(jié)點(diǎn)入棧
//        }
//        return result;
//    }
//}

至此，我們完成了第一步，接下來是第二步，用另一個(gè)棧來反序：

//class Solution {
//    public List<Integer> postorderTraversal(TreeNode root) {
//        List<Integer> result = new LinkedList<>();
//        if (root == null) return result;
//
//        Stack<TreeNode> toVisit = new Stack<>();
          Stack<TreeNode> reversedStack = new Stack<>();
//        toVisit.push(root);
//        TreeNode cur;
//
//        while (!toVisit.isEmpty()) {
//            cur = toVisit.pop();
              reversedStack.push(cur);  // result.add(cur.val);
//            if (cur.left != null) toVisit.push(cur.left); // 左節(jié)點(diǎn)入棧
//            if (cur.right != null) toVisit.push(cur.right); // 右節(jié)點(diǎn)入棧
//        }
//
          while (!reversedStack.isEmpty()) {
              cur = reversedStack.pop();
              result.add(cur.val);
          }
//        return result;
//    }
//}

可見，反序只是將原來直接添加到結(jié)果中的值先添加到一個(gè)棧中，最后再將該棧中的元素全部出棧即可。

至此，我們就實(shí)現(xiàn)了雙棧法的后序遍歷，是不是變的和前序遍歷一樣簡單了呢？

雙棧法的簡化——使用Deque

上面我們介紹的雙棧法雖然簡化了迭代法，但是它額外使用了一個(gè)棧，并且需要在最后將反序棧中的元素再一個(gè)個(gè)出棧，添加到結(jié)果集中，顯得比較笨重，不夠優(yōu)雅，我們下面就來試著簡化一下。

既然最后需要逆序輸出，除了用額外的棧來實(shí)現(xiàn)，我們還可以用鏈表本身來實(shí)現(xiàn)——即，每次添加元素時(shí)都添加到鏈表的頭部，這樣，鏈表本身就成為了一個(gè)棧，在java中，LinkedList本身就已經(jīng)實(shí)現(xiàn)了Deque接口，因此，它也可以當(dāng)做雙端隊(duì)列，則，上面的代碼可以簡化成：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        if (root == null) return result;

        Stack<TreeNode> toVisit = new Stack<>();
        toVisit.push(root);
        TreeNode cur;

        while (!toVisit.isEmpty()) {
            cur = toVisit.pop();
            result.addFirst(cur.val);
            if (cur.left != null) toVisit.push(cur.left);
            if (cur.right != null) toVisit.push(cur.right);
        }
        return result;
    }
}

如果你拿它和前序遍歷的迭代法的代碼對比可以發(fā)現(xiàn)，它們唯一的不同就在于這三行：

result.addFirst(cur.val);
if (cur.left != null) toVisit.push(cur.left); 
if (cur.right != null) toVisit.push(cur.right);

這里要注意，addFirst方法是將值添加到鏈表的開頭。

Morris遍歷法

前面我們多次說過，在二叉樹的訪問中，我們最先遇到的是樹的根節(jié)點(diǎn)，因此，前序遍歷方法非常簡單，因?yàn)樗旧砭褪窍热ピL問根節(jié)點(diǎn)，即根->左->右。而在后序遍歷中，為了簡化問題，我們出于同樣的考慮，將后續(xù)遍歷左->右->根的順序先倒置成根->右->左，使得后續(xù)遍歷中也先去訪問根節(jié)點(diǎn)，這樣就將后序遍歷變得和前序遍歷一樣簡單了，所以目前來看，反倒是中序遍歷左->根->右變成最不直觀的了。

那么有沒有辦法像轉(zhuǎn)變后序遍歷一樣，將中序遍歷也轉(zhuǎn)變成先訪問根節(jié)點(diǎn)呢？似乎不太容易，因?yàn)橹行虮闅v的根節(jié)點(diǎn)是在中間訪問的，無論正過來倒過去，都無法最先訪問。

當(dāng)然，萬事不是絕對的，如果我們的二叉樹是一個(gè)偏向二叉樹，每一個(gè)子樹都沒有左節(jié)點(diǎn)呢？那么就有：

左->根->右 => 根->右

這樣我們就能先訪問根節(jié)點(diǎn)了。當(dāng)然，這自然是個(gè)極端的例子，因?yàn)檎Ｇ闆r下二叉樹都不會(huì)長這樣。但是，這為我們提供了一個(gè)思路——既然二叉樹不長這樣，我們可以把它轉(zhuǎn)換成這樣，這也就是Morris遍歷法所做的事情。

那么怎么轉(zhuǎn)換呢，我們知道，中序遍歷需要先去遍歷左子樹，而左子樹中也要按左->根->右的順序去遍歷，所以整個(gè)樹的根節(jié)點(diǎn)必然是接在左子樹的最后一個(gè)右節(jié)點(diǎn)的后面去遍歷，所以，Morris遍歷法的算法偽代碼如下：

current = root;
while(current != null) {
    if(current沒有左節(jié)點(diǎn)) {
        訪問current的值
        current = current.right
    }
    else {
        在current的左子樹中找到最靠右的節(jié)點(diǎn)(rightmost node)
        將current接在這個(gè)rightmost node下面，作為它的右子樹
        current = current.left
    }
}

這個(gè)偽代碼看上去有點(diǎn)抽象，我們來看一個(gè)例子，這個(gè)例子來源于LeetCode：

現(xiàn)在有這么一棵二叉樹：

我們要對它進(jìn)行中序遍歷，需要將它轉(zhuǎn)換成一個(gè)只有右節(jié)點(diǎn)的偏向樹，按照Morris算法，首先1是根節(jié)點(diǎn)，它是現(xiàn)在的current，它存在一個(gè)左子樹：

         2
        / \
       4   5

按照算法，我們需要找到這個(gè)左子樹最靠右的節(jié)點(diǎn)，在這里就是5，接下來就將current作為這個(gè)節(jié)點(diǎn)的右子樹，即：

然后令current為原來根節(jié)點(diǎn)的左節(jié)點(diǎn)，則此時(shí)的current變成了2，則新的current還是存在左節(jié)點(diǎn)，在這里就是4，我們按照同樣的步驟再將當(dāng)前的current接在它的左子樹的最右節(jié)點(diǎn)下面，這里左子樹只有一個(gè)節(jié)點(diǎn)4，所以我們直接作為該節(jié)點(diǎn)的右孩子即可：

到這里，4就沒有左子樹了，則我們進(jìn)入if語句中，訪問當(dāng)前節(jié)點(diǎn)的值，再指向它的右子樹。這樣一路訪問到3這個(gè)節(jié)點(diǎn)，我們發(fā)現(xiàn)它是有左子樹6的，我們再按之前的方式，將3接在6的右子樹上，最后完成遍歷。

所以，綜上看下來，Morris算法的目的就是消滅左子樹，如果根節(jié)點(diǎn)存在左子樹，就將根節(jié)點(diǎn)作為左子樹的最右節(jié)點(diǎn)的右孩子，這是因?yàn)橹行虮闅v中，對于根節(jié)點(diǎn)的訪問，一定是在訪問完左子樹之后的，而左子樹的最右節(jié)點(diǎn)就是左子樹訪問的最后一個(gè)節(jié)點(diǎn)，因?yàn)榇蠹叶及凑?code>左->中->右的順序來遍歷。

有了對上面的過程的理解以及偽代碼，我們再來寫代碼就很容易了：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left == null) { 
                result.add(cur.val);
                cur = cur.right;
            } else {
                TreeNode rightmost = cur.left;
                while (rightmost.right != null) {
                    rightmost = rightmost.right; // 尋找左子樹的最右節(jié)點(diǎn)
                }
                rightmost.right = cur; // 當(dāng)前節(jié)點(diǎn)作為左子樹的最右節(jié)點(diǎn)的右孩子
                TreeNode oldRoot = cur;
                cur = cur.left; // 將左子樹作為新的頂層節(jié)點(diǎn)
                oldRoot.left = null; // 消除左子樹，防止出現(xiàn)無限循環(huán)
            }
        }
        return result;
    }
}

這里一定要注意oldRoot.left = null，這一步的目的就是消除左子樹，同時(shí)它也能防止無限循環(huán)的出現(xiàn)，一定不要忘記這一步。

綜上，你可以把Morris算法理解成不斷將左節(jié)點(diǎn)作為新的頂層節(jié)點(diǎn)從而消滅左子樹的過程，即實(shí)現(xiàn)了：

左->根->右 => 根->右

的轉(zhuǎn)變。

其實(shí)，如果你再倒回去看我們之前中序遍歷的迭代法的做法：

while (cur != null || !toVisit.isEmpty()) {
    while (cur != null) {
        toVisit.push(cur); // 添加根節(jié)點(diǎn)
        cur = cur.left; // 循環(huán)添加左節(jié)點(diǎn)
    }
    cur = toVisit.pop(); // 當(dāng)前棧頂已經(jīng)是最底層的左節(jié)點(diǎn)了，取出棧頂元素，訪問該節(jié)點(diǎn)
    result.add(cur.val);
    cur = cur.right; // 添加右節(jié)點(diǎn)
}

這里，不斷添加左節(jié)點(diǎn)的做法也有點(diǎn)將左->根->右 轉(zhuǎn)變成 根->右 的意思，因?yàn)橐宰钭蟮哪莻€(gè)左節(jié)點(diǎn)為根節(jié)點(diǎn)的樹可不就是只剩下根->右了嘛，然后我們就安心地訪問根節(jié)點(diǎn)，再去訪問它的右節(jié)點(diǎn)了，只是在下一輪右節(jié)點(diǎn)的訪問中，我們還是要不斷地添加左節(jié)點(diǎn)，以實(shí)現(xiàn)“消滅”左節(jié)點(diǎn)的目的?？梢姡聦?shí)上，思想都是相通的。

最后，這里有一點(diǎn)特別值得一提的是，在Morris算法中，我們并沒有使用到棧，因?yàn)槲覀円呀?jīng)將整個(gè)樹調(diào)整成其訪問順序恰好和遍歷順序一致的偏向樹了，所以相比之前使用棧的算法，這種算法更節(jié)約空間。

復(fù)雜度分析

前面我們分析了前序，中序，后序遍歷的各種方法，但是并沒有去分析它們的復(fù)雜度，這里我們一起來看一下：

首先對于時(shí)間復(fù)雜度，由于樹的每一個(gè)節(jié)點(diǎn)我們都是要去遍歷的，所以它是難以優(yōu)化的，都是O(n)，對于Morris算法，這個(gè)復(fù)雜度的計(jì)算要稍微復(fù)雜一點(diǎn)，但是可以證明，它同樣是O(n)。

對于空間復(fù)雜度，對遞歸方法而言，最壞的空間復(fù)雜度是O(n)，平均空間復(fù)雜度是O(log(n))。對于普通的迭代法而言，由于我們使用到了棧，其時(shí)間復(fù)雜度和空間復(fù)雜度一致，都是O(n)，對于Morris算法，由于我們并沒有使用到棧，只使用到臨時(shí)變量，因此其空間復(fù)雜度是O(1)。

總結(jié)

本文介紹了關(guān)于二叉樹的前序，中序，后序遍歷的遞歸和迭代兩個(gè)版本的算法，同時(shí)對于后序遍歷的簡化版本及中序遍歷的Morris算法做出了解釋和說明，其實(shí)Morris算法的思想同樣可以應(yīng)用在前序遍歷和后序遍歷上，只是筆者認(rèn)為前序遍歷和后序遍歷經(jīng)過簡化后已經(jīng)足夠簡單，這里并沒有給出，不然大有探討“茴香豆的茴字有多少種寫法”的嫌疑。

二叉樹的遍歷中重要的是理解節(jié)點(diǎn)的遍歷順序和訪問順序之間的關(guān)系，我們在上面的非遞歸算法中多次提到，由于最先訪問的到的是樹的根節(jié)點(diǎn)，所以很多優(yōu)化都是將訪問順序轉(zhuǎn)換成先訪問根節(jié)點(diǎn)來做的，理解了這一點(diǎn)再去看那些“玄乎”但是能work的代碼，就不會(huì)覺得摸不著頭腦了。

(完)
文章轉(zhuǎn)自：https://segmentfault.com/a/1190000016674584
作者：ChiuCheng

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

二叉樹的前序，中序，后序遍歷方法總結(jié)

二叉樹的前序，中序，后序遍歷方法總結(jié)

前言

前序遍歷

遞歸法

迭代法

中序遍歷

遞歸法

迭代法

后序遍歷

遞歸法

迭代法

雙棧法

雙棧法的簡化——使用Deque

Morris遍歷法

復(fù)雜度分析

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

二叉樹的前序，中序，后序遍歷方法總結(jié)

前言

前序遍歷

遞歸法

迭代法

中序遍歷

遞歸法

迭代法

后序遍歷

遞歸法

迭代法

雙棧法

雙棧法的簡化——使用Deque

Morris遍歷法

復(fù)雜度分析

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

二叉樹的前序，中序，后序遍歷方法總結(jié)