94/144/145-二叉树的遍历

LeetCode 94. Binary Tree Inorder Traversal

LeetCode-94

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

method

中序遍历：左-根-右

• 递归

void inorder(TreeNode* cur, vector<int>& ret) {
    if (cur == nullptr) return;
    inorder(cur->left, ret);
    ret.push_back(cur->val);
    inorder(cur->right, ret);
}
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    inorder(root, ret);
    return ret;
}

• 迭代

1. 一直往左子树深度遍历，期间把元素插入栈中，直到空
   空的话说明到了无左子树的节点，开始弹出元素，同时查看是否有右节点
2. 有右节点，返回步骤1
3. 无右节点，继续弹出元素

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (!root) return ret;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        if (cur) {
            st.push(cur);
            cur = cur->left;
        }
        else {  // cur空，但栈里有元素，就要弹出
            cur = st.top();
            st.pop();
            ret.push_back(cur->val);
            cur = cur->right;
        }
    }
    return ret;
}

LeetCode 144. Binary Tree Preorder Traversal

LeetCode-144

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

method

前序遍历：根-左-右

• 递归法

void preorder(TreeNode* cur, vector<int>& ret) {
    if (cur == nullptr) return;
    ret.push_back(cur->val);
    preorder(cur->left, ret);
    preorder(cur->right, ret);
}
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    preorder(root, ret);
    return ret;
}

• 迭代法

先放右节点，再放左节点，待会取的时候就是先左再右

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

LeetCode 145. Binary Tree Postorder Traversal

LeetCode-145

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

method

后序遍历：左-右-根

• 递归法

void postorder(TreeNode* cur, vector<int>& ret) {
    if (cur == nullptr) return;
    postorder(cur->left, ret);
    postorder(cur->right, ret);
    ret.push_back(cur->val);
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    postOrder(root, ret);
    return ret;
}

• 迭代法

后序左右根，反过来就是根右左，与先序遍历差不多，最后反转就可以了

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (root == nullptr) return ret;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        ret.push_back(cur->val);
        if (cur->left) st.push(cur->left);
        if (cur->right) st.push(cur->right);
    }
    reverse(ret.begin(), ret.end());
    return ret;
}