二叉树的遍历

 // Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

1、递归

// A.前序遍历(DLR, 根左右)
vector<int> res;
void DLR(TreeNode* root) {
    if (root) {
        res.emplace_back(root-> val);
        DLR(root-> left);
        DLR(root -> right);
    }
}

// B.中序遍历(LDR, 左根右)
vector<int> res;
void LDR(TreeNode* root) {
    if (root) {
        LDR(root-> left);
        res.emplace_back(root-> val);
        LDR(root-> right);
    }
}

// C.后序遍历(LRD, 左右根)
vector<int> res;
void LRD(TreeNode* root) {
    if (root) {
        LRD(root -> left);
        LRD(root -> right);
        res.emplace_back(root -> val);
    }
}

2、非递归

// X.层次遍历
vector<int> res;
void levelOrder(TreeNode* root) {
    queue que;
    que.push(root);
    while (!que.empty()) {
        TreeNode* node = que.front();
        que.pop();
        if (!node) {
            continue;
        }
        res.emplace_back(node -> val);
        que.push(node -> left);
        que.push(node -> right);
    }
}

// A.前序遍历
vector<int> res;
void preorderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        if (!node) {
            continue;
        }
        res.emplace_back(node-> val);
        stk.push(node-> right);
        stk.push(node-> left);
    }
}

// B.中序遍历
vector<int> res;
void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    while (cur || !stk.empty()) {
        while (cur) {
            stk.push(cur);
            cur = cur -> left;
        }
        cur = stk.top();
        stk.pop();
        res.push_back(cur -> val);
        cur = cur -> right;
    }
}

// C.后序遍历
vector<int> res;
void postorderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode *node = stk.top();
        stk.pop();
        if (!node) {
            continue;
        }
        res.push_back(node -> val);
        stk.push(node -> left);
        stk.push(node -> right);
    }
    reverse(res.begin(), res.end());
}

3、Morris法

// A.前序遍历
vector<int> res;
void preorderTraversal(TreeNode* cur) {
    TreeNode* pre;
    while (cur) {
        if (cur -> left) {
            pre = cur -> left;
            while (pre -> right && pre -> right != cur) {
                pre = pre -> right;
            }
            if (pre -> right == nullptr) {
                res.emplace_back(cur -> val);
                pre -> right = cur;
                cur = cur -> left;
            } else {
                pre -> right = nullptr;
                cur = cur -> right;
            }
        } else {
            res.emplace_back(cur -> val);
            cur = cur -> right;
        }
    }
}

// B.中序遍历
vector<int> res;
void inorderTraversal(TreeNode* cur) {
    TreeNode* pre;
    while (cur) {
        if (cur -> left) {
            pre = cur -> left;
            while (pre -> right && pre -> right != cur) {
                pre = pre -> right;
            }
            if (pre -> right == nullptr) {
                pre -> right = cur;
                cur = cur -> left;
            } else {
                res.emplace_back(cur -> val);
                pre -> right = nullptr;
                cur = cur -> right;
            }
        } else {
            res.emplace_back(cur -> val);
            cur = cur -> right;
        }
    }
}

// C.后序遍历
vector<int> res;
void postorderTraversal(TreeNode* cur) {
    TreeNode* pre;
    while (cur) {
        if (cur -> right) {
            pre = cur -> right;
            while (pre -> left && pre -> left != cur) {
                pre = pre -> left;
            }
            if (pre -> left == nullptr) {
                res.emplace_back(cur -> val);
                pre -> left = cur;
                cur = cur -> right;
            } else {
                pre -> left = nullptr;
                cur = cur -> left;
            }
        } else {
            res.emplace_back(cur -> val);
            cur = cur -> left;
        }
    }
    reverse(res.begin(), res.end());
}