二叉树有三种遍历方式：前序、中序、后序，用递归的方法来实现这三种遍历方式非常简单，用非递归的方式来实现就有些细节需要注意了

二叉树的前序遍历非递归实现

  • 根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。
  • 即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：
  • 对于任一结点P：
    • 1)访问结点P，并将结点P入栈;
    • 2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
    • 3)直到P为NULL并且栈为空，则遍历结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> preorderTraversal(TreeNode *root)
{
    if (root == nullptr)
        return vector<int>();
    vector<int> res;
    stack<TreeNode *> s;
    TreeNode *cur = root;
    while (cur || !s.empty())
    {
        while (cur)
        {
            res.push_back(cur->val);
            s.push(cur);
            cur = cur->left;
        }
        if (!s.empty())
        {
            cur = s.top();
            s.pop();
            cur = cur->right;
        }
    }
    return res;
}

二叉树的中序遍历非递归实现

  • 根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：
  • 对于任一结点P，
    • 1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
    • 2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
    • 3)直到P为NULL并且栈为空则遍历结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> inorderTraversal(TreeNode *root)
{
    if (root == nullptr)
        return vector<int>();
    vector<int> res;
    stack<TreeNode *> s;
    TreeNode *cur = root;
    while (cur || !s.empty())
    {
        while (cur)
        {
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        res.push_back(cur->val);
        s.pop();
        cur = cur->right;
    }
    return res;
}

二叉树的后序遍历非递归实现

二叉树的后序遍历是最难的，取巧的方法是先做前序遍历，然后把输出数组翻转即可，还有一种方法是记录上个访问的节点

仿照上面的写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
vector<int> postorderTraversal(TreeNode *root)
{
    if (root == nullptr)
        return vector<int>();
    vector<int> res;
    stack<TreeNode *> s;
    TreeNode *cur = root;
    TreeNode *pre = nullptr;
    while (cur || !s.empty())
    {
        while (cur)
        {
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        if (!cur->right || pre == cur->right)
        {
            res.push_back(cur->val);
            pre = cur;
            cur = nullptr;
            s.pop();
        }
        else
        {
            cur = cur->right;
        }
    }
    return res;
}

感觉更好理解的写法：

  • 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。
  • 如果P不存在左孩子和右孩子，则可以直接访问它；
  • 或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。因为访问顺序一定是：左（如果有的话）-右（如果有的话）-根。
  • 若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root){
        vector<int> ans;
        if (root == nullptr) return ans;
        stack<TreeNode *> s;
        TreeNode *cur;
        TreeNode *pre = nullptr;
        s.push(root);
        while (!s.empty()){
            cur = s.top();
            if ((!cur->left && !cur->right) ||
                (pre && (pre == cur->left || pre == cur->right))) {
                ans.push_back(cur->val);
                pre = cur;
                s.pop();
            } else {
                if (cur->right) s.push(cur->right);
                if (cur->left) s.push(cur->left);
            }
        }
        return ans;
    }
};