LeeCode-94. 二叉樹的中序遍歷

基本概念

看二叉樹基本的結(jié)構(gòu)左-中-右三個(gè)節(jié)點(diǎn)，中間為Root，左邊為Left，右邊為Right。按順序排列的話有C(3,2)=6種，其中左右，右左算法類似。以中間Root為參考，固定左-右，則排序 左-中-右 為中序遍歷，中-左-右 為先序遍歷，左-右-中 為后序遍歷。

解題思路

題目要求中序遍歷，即對(duì)于所有的節(jié)點(diǎn)，都是左-中-右的順序遍歷所有節(jié)點(diǎn)，考慮到二叉樹結(jié)構(gòu)本身的特殊性，采用指針依次訪問，比較難以遍歷全局。考慮到整棵樹本身可以看作一個(gè)基本節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)本身又是一個(gè)基本節(jié)點(diǎn)，如下圖所示，類似想到遞歸調(diào)用。先寫出基本結(jié)構(gòu)的調(diào)用順序，再依次對(duì)各子節(jié)點(diǎn)做遞歸調(diào)用。

實(shí)現(xiàn)代碼

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    if (root)
    {
        if (root->left)
        {
            auto temp = inorderTraversal(root->left);
            result.insert(result.end(), temp.begin(), temp.end());
        }

        result.push_back(root->val);

        if (root->right)
        {
            auto temp = inorderTraversal(root->right);
            result.insert(result.end(), temp.begin(), temp.end());
        }

    }
    return result;
}