最优雅的二叉树非递归遍历模板

LeetCode 144. 二叉树的前序遍历 ????

先压栈的是右孩子，再是左孩子，由于栈先进后出的特点，先取出来的就是左孩子，然后是右孩子，满足 根 - 左 - 右。

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

LeetCode 94. 二叉树的中序遍历 ????

直接模拟中序遍历的过程。

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

LeetCode 145. 二叉树的后序遍历 ????

有点抽象，总之只需理解 根 - 右 - 左 逆过来就是 左 - 右 - 根。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root)
            return res;
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while (!s.empty()) {
            node = s.top();
            s.pop();
            res.push_back(node->val);
            if (node->left)
                s.push(node->left);
            if (node->right)
                s.push(node->right);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

最后

以上就是高挑金针菇为你收集整理的最优雅的二叉树非递归遍历模板的全部内容，希望文章能够帮你解决最优雅的二叉树非递归遍历模板所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。