结构体定义

Leetcode中TreeNode结构体定义如下:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

二叉树的前序遍历

递归版本:

class Solution {
public:

    vector<int> res;
    vector<int> preorderTraversal(TreeNode* root) {
        if(!root) return res;
        res.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return res;
    }
};

迭代版本:

class Solution {
public:

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stack;
        if(root){
            stack.push(root);
        }
        while(!stack.empty()){
            TreeNode* curr = stack.top();
            stack.pop();
            res.push_back(curr->val);
            if(curr->right != nullptr){
                stack.push(curr->right);
            }
            if(curr->left != nullptr){
                stack.push(curr->left);
            }
        }
        return res;
    }
};

二叉树的中序遍历

递归版本:

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

迭代版本:

class Solution {
public:
    vector<int> res;
    stack<TreeNode*> stack;
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* curr = root;
        while(!stack.empty() || curr != NULL){
            //找到最左侧节点
            while(curr != NULL){
                stack.push(curr);
                curr = curr->left;
            }
            //此时栈顶为最左节点,curr为最左节点的左孩子节点
            TreeNode* top = stack.top();
            stack.pop();
            res.push_back(top->val);
            //判断top节点是否存在右子树
            if(top->right != NULL)
                curr = top->right;
        }
        return res;
    }
};

二叉树后序遍历

递归版本:

class Solution {
public:
    vector<int> res;
    vector<int> postorderTraversal(TreeNode* root) {
        // 为空则直接返回
        if(root == NULL)
            return res;
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        res.push_back(root->val);
        return res;
    }
};

递归版本:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> stk;
        if(root != NULL)
            stk.push(root);
        // curr存储当前退出栈的结点
        TreeNode* curr = root;
        while(!stk.empty())
        {
            TreeNode* top = stk.top();
            if(top->left != NULL && top->left != curr && top->right != curr)
                stk.push(top->left);
            else if(top->right != NULL && top->right != curr)
                stk.push(top->right);
            // 当左右子树都处理过或者不存在情况下,说明此结点可以弹栈
            else
            {
                ans.push_back(top->val);
                stk.pop();
                curr = top;
            }
        }
        return ans;
    }

};

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

2021年6月 上一篇
2021年5月 下一篇