二叉树的中序遍历

大忽悠爱学习

发布于 2021-11-15 02:14:54

16700

代码可运行

文章被收录于专栏：c++与qt学习c++与qt学习

运行总次数：0

代码可运行

解法1：递归解法

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        display(root, ret);
        return ret;
    }
    //递归写法
    void display(TreeNode* root,vector<int>& ret)
    {
        if (root == NULL)
            return;
        display(root->left, ret);
        ret.push_back(root->val);
        display(root->right, ret);
    }
};

解法2：颜色标记法

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root)
    {
        stack<pair<TreeNode*, string>> st;
        vector<int> ret;
        if (root == NULL)
            return ret;
        st.push({ root,"white" });
       //或者这样写： st.push((make_pair(root, "white")));
        while (!st.empty())
        {
            pair < TreeNode*, string > p= st.top();
            st.pop();
            if (p.first == NULL)
                continue;
            if (p.second == "white")
            {
                p.second = "grey";
                st.push({ p.first->right,"white" });
                st.push(p);
                st.push({ p.first->left,"white" });
            }
            else
                ret.push_back(p.first->val);
        }
        return ret;
    }
};

每一次有新节点入栈，都会设置他的颜色为白色，目的是为了在该节点下次出栈的时候，查看其左右孩子是否存在，存在的话压入栈中，再设置为灰色，下一次出栈就直接输出

官方栈解法：

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