二叉樹遍歷方法大全（包含莫里斯遍歷）

前言

二叉樹的遍歷可能大家都比較熟悉了，這篇文章主要介紹了三種二叉樹的遍歷方法——遞歸、迭代和莫里斯遍歷，他們各自有各自的特點。其中最重要的是莫里斯遍歷，相對于前兩種方法比較少見，只需要固定的空間就可以完成迭代遍歷。這篇文章將會結(jié)合動圖，帶你了解關(guān)于樹遍歷的知識。

簡介

我們通常希望通過訪問樹的每個節(jié)點來處理二叉樹，每次執(zhí)行特定的操作，例如打印節(jié)點的內(nèi)容、得到樹的所有節(jié)點的總和或者要找到最大的值。以某種順序訪問所有節(jié)點的過程稱為遍歷，僅遍歷樹中每個節(jié)點一次的遍歷稱為樹節(jié)點的枚舉。某些應(yīng)用不需要以任何特定順序訪問節(jié)點，只要每個節(jié)點被精確訪問一次即可；有些應(yīng)用，必須按保留某些關(guān)系的順序訪問節(jié)點。

線性數(shù)據(jù)結(jié)構(gòu)（如數(shù)組、堆棧、隊列和鏈表）只有一種讀取數(shù)據(jù)的方法，但是像樹這樣的分層數(shù)據(jù)結(jié)構(gòu)可以以不同的方式遍歷。

遍歷種類

根據(jù)我們遍歷樹的順序，我們把遍歷分成三種，分別是：

  • 中序遍歷
  • 前序遍歷
  • 后序遍歷

這些遍歷方式和樹的結(jié)構(gòu)有關(guān)。

tree.png

中序遍歷

  1. 先遍歷左子樹
  2. 再遍歷父節(jié)點
  3. 最后遍歷右子樹

圖片中的中序遍歷結(jié)果應(yīng)該是[4,2,5,1,6,3,7]

前序遍歷

  1. 先遍歷父節(jié)點
  2. 再遍歷左子樹
  3. 最后遍歷右子樹

圖片中的前序遍歷結(jié)果應(yīng)該是[1,2,4,5,3,6,7]

后序遍歷

  1. 先遍歷左子樹
  2. 再遍歷右子樹
  3. 最后遍歷父節(jié)點

圖中的后序遍歷結(jié)果應(yīng)該是[4,5,2,6,7,3,1]

代碼實現(xiàn)

首先定義樹的結(jié)構(gòu)

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) { val = x; }

}

在代碼實現(xiàn)里面我們要返回按照特定遍歷順序依次遍歷的節(jié)點

中序?qū)崿F(xiàn)

中序遞歸

按照中序遍歷的定義可以很容易用遞歸來實現(xiàn)

public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    List<Integer> res = new ArrayList<>();  // 保存最后的結(jié)果
    inorderTraversal(root, res);
    return res;
}

public void inorderTraversal(TreeNode root, List<Integer> res) {
    if (root == null) {
        return;
    }
    inorderTraversal(root.left, res);   // 遍歷左子樹
    res.add(root.val);                  // 遍歷父節(jié)點
    inorderTraversal(root.right, res);  // 遍歷右子樹
}

中序迭代

采用迭代的方法就有點復(fù)雜了，需要借助額外的數(shù)據(jù)結(jié)構(gòu)——棧。

這個方法的思路是：

先從父結(jié)點遍歷左子節(jié)點，一直遍歷到不再存在左子節(jié)點，然后從棧頂開始檢查，對剛才遍歷的節(jié)點進行逆向遍歷，找到每一個節(jié)點的右子節(jié)點，如果這些右子節(jié)點有左節(jié)點就繼續(xù)壓入棧中（相當(dāng)于下次遍歷要從這個右子節(jié)點的左子樹開始），繼續(xù)上面的過程。

整個相當(dāng)于深度優(yōu)先遍歷，從每個節(jié)點的左節(jié)點遍歷，遍歷父節(jié)點，最后遍歷右節(jié)點。棧的作用相當(dāng)于記住了上次遍歷的位置，用來保存下次應(yīng)該開始遍歷的節(jié)點。

inorder.png
public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    Stack<TreeNode> stack = new Stack<>();
    List<Integer> res = new ArrayList<>();  // 遍歷結(jié)果
    stack.push(root);

    TreeNode cur = root.left;
    while (!stack.isEmpty() || cur != null) {
        while (cur != null) {   // 先將所有的左節(jié)點的內(nèi)容壓入棧中
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();    // 出棧的時候進行遍歷
        res.add(cur.val);
        cur = cur.right;     // 代表開始遍歷右子樹
    }
    return res;
}

中序莫里斯迭代

莫里斯遍歷不需要遞歸或者臨時的?？臻g就可以完成遍歷，空間復(fù)雜度是常數(shù)。但是為了解決從子節(jié)點找到父節(jié)點的問題，需要臨時修改樹的結(jié)構(gòu)，在遍歷完成之后復(fù)原成原來的樹結(jié)構(gòu)。

整個遍歷的過程中只需要兩個指針——當(dāng)前指針cur和臨時前驅(qū)指針prev，具體的過程如下

  1. 如果左子節(jié)點是空，錄入當(dāng)前節(jié)點，當(dāng)前指針cur指向右子節(jié)點
  2. 如果左子節(jié)點不是空，遍歷左子節(jié)點的最右側(cè)右子節(jié)點，找到最右側(cè)葉節(jié)點，在尋找的過程中可能出現(xiàn)兩種情況：
    • 如果遍歷到的葉節(jié)點的右子節(jié)點是空，把葉節(jié)點的右子節(jié)點指向cur節(jié)點，cur移向左子節(jié)點
    • 如果遍歷到的葉節(jié)點的右子節(jié)點是cur節(jié)點，表示原來的葉節(jié)點到cur節(jié)點連接已經(jīng)存在，現(xiàn)在遍歷結(jié)束了，需要復(fù)原，置節(jié)點的右子節(jié)點為空，在錄入了cur節(jié)點之后，cur移到自己的右子節(jié)點
  3. 重復(fù)上面兩步直到當(dāng)前節(jié)點為空

其中最不好理解的是第二步，遍歷左子樹的右節(jié)點的過程中，只有當(dāng)左子樹沒有建立到父節(jié)點的連接的時候，才能最后遍歷到盡頭，達到盡頭之后需要和父節(jié)點連接起來，當(dāng)cur遍歷到這個葉節(jié)點的時候才能回到正確的父節(jié)點的位置。

當(dāng)當(dāng)前節(jié)點cur遍歷完了左子樹回到父節(jié)點的時候，多余的連接還是存在的，需要移除這個連接，而方法就是和建立連接一樣遍歷左子樹找到最右側(cè)節(jié)點，這個時候判斷的依據(jù)就不能是右節(jié)點為空，必須是左子節(jié)點的最右節(jié)點等于當(dāng)前節(jié)點，相當(dāng)于找到循環(huán)的起點，然后在這個地方切斷聯(lián)系。

morris.gif

代碼實現(xiàn)：

public List<Integer> inorderTraversal(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    TreeNode cur = root;    // 記錄當(dāng)前節(jié)點位置
    List<Integer> res = new ArrayList<>();
    while (cur != null) {
        if (cur.left == null) {   // 左節(jié)點為空，移到右子節(jié)點
            res.add(cur.val);
            cur = cur.right;
        }  else {
            TreeNode prev = cur.left;
            while (prev.right != null && prev.right != cur) { // 遍歷到左子樹的最右側(cè)節(jié)點
                prev = prev.right;
            }
            if (prev.right == null) {        // 建立返回父節(jié)點連接
                prev.right = cur;
                cur = cur.left;
            } else {                        // 左子樹建立了連接，說明遍歷完了，可以拆除連接
                res.add(cur.val);           // 中序遍歷錄入當(dāng)前節(jié)點
                prev.right = null;
                cur = cur.right;
            }
        }
    }
    return res;
}

時間復(fù)雜度分析：莫里斯遍歷的空間復(fù)雜度是常數(shù)，這個比較好理解，但是時間復(fù)雜度為什么是O(n)呢？明明在代碼里面有個嵌套的循環(huán)可能會提高時間復(fù)雜度：

while (prev.right != null && prev.right != cur) { // 遍歷到左子樹的最右側(cè)節(jié)點
    prev = prev.right;
}

可是如果在圖中模擬一下這個循環(huán)就會發(fā)現(xiàn)其實在尋找前驅(qū)節(jié)點的過程中，所有的節(jié)點其實最多只被遍歷了兩遍！比如對于節(jié)點1，在尋找前驅(qū)節(jié)點的時候遍歷了2和5；當(dāng)cur從5回到1之后，又遍歷了一遍2和5，至此2和5在所有尋找前驅(qū)節(jié)點的過程中各遍歷了兩邊，而在尋找2..7的前驅(qū)節(jié)點的時候，都沒有遍歷到2和5（除去了從2和5本身開始查找前驅(qū)節(jié)點時對自己的遍歷），所以2和5總體在前驅(qū)搜索的過程中只有兩次，加上他們自身的遍歷，也就只有3次。綜合來說，樹的每個節(jié)點的遍歷次數(shù)最多都是3次，所以時間復(fù)雜度是O(n)級別的。

traverse.png

前序?qū)崿F(xiàn)

前序遞歸

和中序的遞歸差不多，只有一行代碼的區(qū)別：

public List<Integer> preorderTraversal(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    List<Integer> res = new ArrayList<>();  // 保存最后的結(jié)果
    preorderTraversal(root, res);
    return res;
}

public void preorderTraversal(TreeNode root, List<Integer> res) {
    if (root == null) {
        return;
    }
    res.add(root.val);                  // 遍歷父節(jié)點   注意這行代碼提前了
    preorderTraversal(root.left, res);   // 遍歷左子樹
    preorderTraversal(root.right, res);  // 遍歷右子樹
}

前序迭代

直接根據(jù)中序迭代的方法，將記錄遍歷元素的時機改為了在入棧的時候就記錄，也就是將父節(jié)點計入數(shù)組的時間提前了。

public List<Integer> preorderTraversal3(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    Stack<TreeNode> stack = new Stack<>();
    List<Integer> res = new ArrayList<>();  // 遍歷結(jié)果
    stack.push(root);

    TreeNode cur = root.left;
    res.add(root.val);      // 記錄根節(jié)點元素
    while (!stack.isEmpty() || cur != null) {
        while (cur != null) {   // 先將所有的左節(jié)點的內(nèi)容壓入棧中
            stack.push(cur);
            res.add(cur.val);  // 這里在入棧的時候就要記錄遍歷的元素
            cur = cur.left;
        }
        cur = stack.pop();
        cur = cur.right;     // 代表開始遍歷右子樹
    }
    return res;
}

前序莫里斯

和中序莫里斯遍歷的代碼也基本一樣，只不過當(dāng)左子節(jié)點存在的時候，添加節(jié)點元素的位置從拆除多余連接的時候變成了建立連接的時候，也就是在移動cur指針之前就得記錄節(jié)點，保證當(dāng)前指向的節(jié)點是最先記錄的，左右子樹的節(jié)點要靠后，并且不能重復(fù)記錄元素。

public List<Integer> preorderTraversal(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    TreeNode cur = root;    // 記錄當(dāng)前節(jié)點位置
    List<Integer> res = new ArrayList<>();
    while (cur != null) {
        if (cur.left == null) {   // 左節(jié)點為空，移到右子節(jié)點
            res.add(cur.val);
            cur = cur.right;
        }  else {
            TreeNode prev = cur.left;
            while (prev.right != null && prev.right != cur) { // 遍歷到左子樹的最右側(cè)節(jié)點
                prev = prev.right;
            }
            if (prev.right == null) {        // 建立返回父節(jié)點連接
                prev.right = cur;
                res.add(cur.val);           // 注意添加元素到數(shù)組的代碼位置移到了這里
                cur = cur.left;
            } else {                        // 左子樹建立了連接，說明遍歷完了，可以拆除連接
                prev.right = null;
                cur = cur.right;
            }
        }
    }
    return res;
}

后序?qū)崿F(xiàn)

后序遞歸

后序遞歸和前中遞歸的實現(xiàn)差不多，只需要把錄入元素的時機放在遍歷左右子樹之后就行了

public List<Integer> postorderTraversal(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    List<Integer> res = new ArrayList<>();  // 保存最后的結(jié)果
    postorderTraversal(root, res);
    return res;
}

public void postorderTraversal(TreeNode root, List<Integer> res) {
    if (root == null) {
        return;
    }
    postorderTraversal(root.left, res);   // 遍歷左子樹
    postorderTraversal(root.right, res);  // 遍歷右子樹
    res.add(root.val);                  // 遍歷父節(jié)點
}

還有另外一種遞歸可能會對我們后序迭代算法略有啟發(fā)：我們可以通過將遍歷父節(jié)點操作放在最前面，然后交換遍歷左右子樹的順序，得到反轉(zhuǎn)的后序遍歷結(jié)果，最后反轉(zhuǎn)一下就能得到正確的遍歷結(jié)果。

public List<Integer> postorderTraversal(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    List<Integer> res = new ArrayList<>();  // 保存最后的結(jié)果
    postorderTraversal(root, res);
    Collections.reverse(res);             // 反轉(zhuǎn)數(shù)組
    return res;
}

public void postorderTraversal(TreeNode root, List<Integer> res) {
    if (root == null) {
        return;
    }
    res.add(root.val);                  // 遍歷父節(jié)點
    postorderTraversal(root.right, res);  // 遍歷右子樹
    postorderTraversal(root.left, res);   // 遍歷左子樹
}

后序迭代

后序迭代就比較巧妙了，利用上面講到的修改前序遍歷的遍歷左右子樹的順序，移植到迭代過程中的棧的操作，把原來的所有的right改成left，原來的left改成right

public List<Integer> postorderTraversal(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    Stack<TreeNode> stack = new Stack<>();
    List<Integer> res = new ArrayList<>();  // 遍歷結(jié)果
    stack.push(root);

    TreeNode cur = root.right;
    res.add(root.val);  // 添加根節(jié)點，反轉(zhuǎn)后變成最后元素
    while (!stack.isEmpty() || cur != null) {
        while (cur != null) {   // 先將所有的右節(jié)點的內(nèi)容壓入棧中
            stack.push(cur);
            res.add(cur.val);   // 添加當(dāng)前遍歷的節(jié)點
            cur = cur.right;
        }
        cur = stack.pop();
        cur = cur.left;     // 代表開始遍歷左子樹
    }
    Collections.reverse(res); // 反轉(zhuǎn)最后的結(jié)果
    return res;
}

后序莫里斯迭代

修改后序莫里斯迭代的思路其實和上面修改后序迭代的思路一樣

  1. 把前序莫里斯遍歷的代碼粘貼過來
  2. 把原來所有的right改成left，把原來所有的left改成right
  3. 返回結(jié)果之前反轉(zhuǎn)一下數(shù)組

這種后序迭代遍歷的核心思路都是通過交換前序遍歷中遍歷左右子樹的順序，達到完全逆轉(zhuǎn)后序遍歷的結(jié)果，最后反轉(zhuǎn)得到正確的結(jié)果。

public List<Integer> postorderTraversal(TreeNode root) {
    if (root == null) {
        return new ArrayList<>();
    }

    TreeNode cur = root;    // 記錄當(dāng)前節(jié)點位置
    List<Integer> res = new ArrayList<>();
    while (cur != null) {
        if (cur.right == null) {   // 右節(jié)點為空，移到左子節(jié)點
            res.add(cur.val);
            cur = cur.left;
        }  else {
            TreeNode prev = cur.right;
            while (prev.left != null && prev.left != cur) { // 遍歷右子樹的最左側(cè)節(jié)點
                prev = prev.left;
            }
            if (prev.left == null) {        // 建立返回父節(jié)點連接
                prev.left = cur;
                res.add(cur.val);           // 添加元素到數(shù)組
                cur = cur.right;
            } else {                        // 右子樹建立了連接，說明遍歷完了，可以拆除連接
                prev.left = null;
                cur = cur.left;
            }
        }
    }
    Collections.reverse(res);   // 最后要反轉(zhuǎn)數(shù)組得到最后的結(jié)果
    return res;
}

總結(jié)

總的來說二叉樹的遍歷是非常重要也是非常基礎(chǔ)的知識，大部分人都能夠輕松的寫出遞歸的做法，遞歸的代碼是最簡潔明了容易理解的。

迭代的解決方法比較少見，需要額外的數(shù)據(jù)結(jié)構(gòu)，循環(huán)的邏輯也不是那么容易理解，但是在面試或者OJ系統(tǒng)里面可能會出現(xiàn)的比較多。

關(guān)于莫里斯遍歷，可能大多數(shù)人都沒有聽說過這種巧妙的遍歷方法，需要修改樹的結(jié)構(gòu)以降低空間開銷，同時在遍歷結(jié)束之后還要復(fù)原樹的結(jié)構(gòu)。這種遍歷相對于上面的迭代更加難以理解，但是它只需要兩個變量就可以完成遍歷的特點令人影響深刻。

參考

Morris Traversal方法遍歷二叉樹（非遞歸，不用棧，O(1)空間）
What is Morris traversal?
二叉樹的前序、中序、后序遍歷—迭代方法

更多精彩內(nèi)容請看我的個人博客

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

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

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