二叉树理论基础与遍历实现

C++ 实现（中序遍历）左，中，右

class Solution {
public:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> result;
        traverse(root, result);
        return result;
    }
private:
    void traverse(TreeNode* node, std::vector<int>& res) {
        if (node == nullptr) return; // 递归终止条件
        traverse(node->left, res); // 左
        res.push_back(node->val); // 中
        traverse(node->right, res); // 右
    }
};

C++ 实现（后序遍历）左，右，中

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traverseTree(root, result);
        return result;
    }
    void traverseTree(TreeNode* root, vector<int>& result) {
        if (root == nullptr) return;
        traverseTree(root->left, result);
        traverseTree(root->right, result);
        result.push_back(root->val);
    }
};

二叉树的迭代遍历

重点

• 手动实现一遍，按照实现步骤转换成代码，就理解了
• 就是一个栈，放进放出。
• 只用栈，所有的循环判断依靠的是栈本身。弹出顺序和使用顺序一致。
• 中序遍历使用一个栈无法直接实现，就是因为栈顶节点和要使用节点不一致。循环判断条件依靠的是辅助指定的指针和栈本身。

C++ 实现（前序遍历）中，左，右

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

C++ 实现（中序遍历）左，中，右

一直向左走到底（入栈），遇到空就弹出栈顶（即'回溯'），访问该节点，然后转向其右子树。

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

因为栈放进去之后，所有元素都没有区别，只有栈顶获取，弹出，所以需要另一个指针来确定栈顶的元素是否要使用。

C++ 实现（后序遍历）左，右，中

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

二叉树的统一迭代法

重点

• 两种方法
• 第一种，一个节点可以处理的范围是自己和左右孩子（该节点的根，该节点处理不到）。节点分两部分完成遍历，第一次通过节点来获得左右孩子，第二次看到第一次处理过的标志直接处理本节点。
• 第二种，给一个 pair，first 表示节点，second 表示是否使用过。
• 本质是一种方式，就是让节点分两步进行。没处理过的先处理，处理过的直接用。

C++ 实现（前序遍历）使用 null 表示使用

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

C++ 实现（中序遍历）使用 null 表示使用

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root == nullptr) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* temp = st.top();
            if (temp) {
                st.pop();
                if (temp->right) st.push(temp->right);
                st.push(temp);
                st.push(NULL);
                if (temp->left) st.push(temp->left);
            } else {
                st.pop();
                temp = st.top();
                st.pop();
                result.push_back(temp->val);
            }
        }
        return result;
    }
};

C++ 实现（后序遍历）使用 null 表示使用

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root == nullptr) return {};
        st.push(root);
        while (!st.empty()) {
            TreeNode* temp = st.top();
            if (temp) {
                st.push(nullptr);
                if (temp->right) st.push(temp->right);
                if (temp->left) st.push(temp->left);
            } else {
                st.pop();
                temp = st.top();
                st.pop();
                result.push_back(temp->val);
            }
        }
        return result;
    }
};

C++ 实现（中序遍历）使用 pair 携带一个 bool 来确定元素状态

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<pair<TreeNode*, bool>> st;
        if (root != nullptr) st.push(make_pair(root, false));
        while (!st.empty()) {
            auto node = st.top().first;
            auto visited = st.top().second;
            st.pop();
            if (visited) {
                result.push_back(node->val);
                continue;
            }
            if (node->right) st.push(make_pair(node->right, false));
            st.push(make_pair(node, true));
            if (node->left) st.push(make_pair(node->left, false));
        }
        return result;
    }
};

二叉树层序遍历

重点

• 逐层

C++ 实现

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if (root == nullptr) return result;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                TreeNode* temp = que.front();
                que.pop();
                vec.push_back(temp->val);
                if (temp->left) que.push(temp->left);
                if (temp->right) que.push(temp->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

总结

• 也是特点吧
• 遍历的时候，如果单一使用栈或者队列，函数体内的循环逻辑围绕的就是栈或队列是否为空
• 如果是中序迭代，遍历需要一个指针来辅助，函数体内的循环逻辑围绕的就是栈是否空以及指针是否为空
• 这样便于记忆二叉树的遍历逻辑