[LeetCode] 94. Binary Tree Inorder Traversal 二叉樹的中序遍歷

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

二叉樹的中序遍歷順序?yàn)樽?根-右，可以有遞歸和非遞歸來解，其中非遞歸解法又分為兩種，一種是使用棧來接，另一種不需要使用棧。我們先來看遞歸方法，十分直接，對左子結(jié)點(diǎn)調(diào)用遞歸函數(shù)，根節(jié)點(diǎn)訪問值，右子節(jié)點(diǎn)再調(diào)用遞歸函數(shù)，代碼如下：

解法一：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode *root, vector<int> &res) {
        if (!root) return;
        if (root->left) inorder(root->left, res);
        res.push_back(root->val);
        if (root->right) inorder(root->right, res);
    }
};

下面再來看非遞歸使用棧的解法，也是符合本題要求使用的解法之一，需要用棧來做，思路是從根節(jié)點(diǎn)開始，先將根節(jié)點(diǎn)壓入棧，然后再將其所有左子結(jié)點(diǎn)壓入棧，然后取出棧頂節(jié)點(diǎn)，保存節(jié)點(diǎn)值，再將當(dāng)前指針移到其右子節(jié)點(diǎn)上，若存在右子節(jié)點(diǎn)，則在下次循環(huán)時又可將其所有左子結(jié)點(diǎn)壓入棧中。這樣就保證了訪問順序?yàn)樽?根-右，代碼如下：

解法二： 

// Non-recursion
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top(); s.pop();
            res.push_back(p->val);
            p = p->right;
        }
        return res;
    }
};

下面這種解法跟 Binary Tree Preorder Traversal 中的解法二幾乎一樣，就是把結(jié)點(diǎn)值加入結(jié)果 res 的步驟從 if 中移動到了 else 中，因?yàn)橹行虮闅v的順序是左-根-右，參見代碼如下：

解法三：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (!s.empty() || p) {
            if (p) {
                s.push(p);
                p = p->left;
            } else {
                p = s.top(); s.pop();
                res.push_back(p->val);
                p = p->right;
            }
        }
        return res;
    }
};

下面來看另一種很巧妙的解法，這種方法不需要使用棧，所以空間復(fù)雜度為常量，這種非遞歸不用棧的遍歷方法有個專門的名字，叫 Morris Traversal，在介紹這種方法之前，先來引入一種新型樹，叫 Threaded binary tree，這個還不太好翻譯，第一眼看上去以為是叫線程二叉樹，但是感覺好像又跟線程沒啥關(guān)系，后來看到網(wǎng)上有人翻譯為螺紋二叉樹，但博主認(rèn)為這翻譯也不太敢直視，很容易讓人聯(lián)想到為計(jì)劃生育做出突出貢獻(xiàn)的某世界著名品牌，后經(jīng)熱心網(wǎng)友提醒，應(yīng)該叫做線索二叉樹。先來看看維基百科上關(guān)于它的英文定義：

A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.

就是說線索二叉樹實(shí)際上是把所有原本為空的右子節(jié)點(diǎn)指向了中序遍歷順序之后的那個節(jié)點(diǎn)，把所有原本為空的左子節(jié)點(diǎn)都指向了中序遍歷之前的那個節(jié)點(diǎn)。那么這道題跟這個線索二叉樹又有啥關(guān)系呢？由于既不能用遞歸，又不能用棧，那如何保證訪問順序是中序遍歷的左-根-右呢。原來需要構(gòu)建一個線索二叉樹，需要將所有為空的右子節(jié)點(diǎn)指向中序遍歷的下一個節(jié)點(diǎn)，這樣中序遍歷完左子結(jié)點(diǎn)后，就能順利的回到其根節(jié)點(diǎn)繼續(xù)遍歷了。具體算法如下：

1. 初始化指針 cur 指向 root

2. 當(dāng) cur 不為空時

　 - 如果 cur 沒有左子結(jié)點(diǎn)

　     a) 打印出 cur 的值

　　  b) 將 cur 指針指向其右子節(jié)點(diǎn)

　 - 反之

　    將 pre 指針指向 cur 的左子樹中的最右子節(jié)點(diǎn)　

　　　  * 若 pre 不存在右子節(jié)點(diǎn)

　　　       a) 將其右子節(jié)點(diǎn)指回 cur

　　　　    b) cur 指向其左子節(jié)點(diǎn)

　　　  * 反之

　　　　　 a) 將 pre 的右子節(jié)點(diǎn)置空

　　　　　 b) 打印 cur 的值

　　　　　 c) 將 cur 指針指向其右子節(jié)點(diǎn)

解法四：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> res;
        if (!root) return res;
        TreeNode *cur, *pre;
        cur = root;
        while (cur) {
            if (!cur->left) {
                res.push_back(cur->val);
                cur = cur->right;
            } else {
                pre = cur->left;
                while (pre->right && pre->right != cur) pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    cur = cur->left;
                } else {
                    pre->right = NULL;
                    res.push_back(cur->val);
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};

其實(shí) Morris 遍歷不僅僅對中序遍歷有用，對先序和后序同樣有用。所以對二叉樹的三種常見遍歷順序(先序，中序，后序)就有三種解法(遞歸，非遞歸，Morris 遍歷)，總共有九段代碼呀，熟練掌握這九種寫法才算初步掌握了樹的遍歷挖

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(94.二叉樹的中序遍歷)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)二叉樹的中序遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！