二叉树的迭代遍历

二叉树的迭代遍历

递归能做的，栈也能做！

每次递归调用把函数的局部变量、返回值、参数等压入调用栈中，函数返回时弹出上一次递归的各项参数，因此可以用栈代替递归实现树的遍历。

前序遍历（中左右）

以一个例子说明：

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

需要注意的是，对当前节点的处理，总是先将右子节点压入栈，再将左子节点压入栈，目的是为了以中左右的顺序弹出元素

后序遍历（左右中）

注意：直接在前序遍历基础上更改入栈顺序，中左右，得到的数组实际遍历顺序是中右左，翻转后得到所要求得后序遍历顺序，左右中。

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

中序遍历（左中右）

中序遍历迭代法实现的难点是访问顺序与处理顺序不一致，先访问到中间节点，而先处理的是左子节点。借助指针访问节点，用栈处理节点。

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

• 总结