本文介绍二叉树的遍历方法和具体代码实现。

1 二叉树的遍历方法

二叉树的遍历方法根据访问根结点的先后顺序分为先序、中序、后序遍历。
下面1.1，1.2，1.3节将分别介绍各种遍历方式的递归实现和非递归实现方法。

1.1 二叉树的先序遍历

二叉树先序遍历的过程为：遍历根结点，先序遍历左子树，先序遍历右子树。

1.1.1 二叉树先序遍历的递归实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        preorder(root);
        return res;
    }
    void preorder(TreeNode* root) {
        if (root == NULL) {
            return;
        }
        res.push_back(root->val);
        preorder(root->left);
        preorder(root->right);
    }
private:
    vector<int> res;
};

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

先序遍历的非递归实现方式采用DFS的遍历算法，使用栈来保存中间结果。

  1. 方法1：传统方式，首先将根结点添加至栈中，然后循环添加根结点的左孩子结点。
    当左孩子为空时，弹出栈顶结点，并将栈顶的右孩子结点作为根结点重复进行该过程。
    因为是先序遍历，因此所有结点在进栈前进行访问。具体代码如下所示：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == NULL) {
            return res;
        }
        stack<TreeNode*> stk;
        TreeNode* top = root;
        while (!stk.empty() || top) {
            while (top) {
                res.push_back(top->val);
                stk.push(top);
                top = top->left;
            }
            top = stk.top();
            stk.pop();
            top = top->right;
        }
        return res;
    }
};
  1. 方法2：因为栈的特性是后进先出。入栈和出栈的顺序相反，因此可以利用这一特性简化代码流程：
    具体方法为：在根结点出栈前进行访问，然后分别将其右孩子和左孩子进栈。循环进行，直到栈为空为止。
    这样就会在访问的时候先访问左孩子再访问右孩子。具体实现方式如下：
 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

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

            if (top->right) {
                stk.push(top->right);
            }

            if (top->left) {
                stk.push(top->left);
            }
        }
        return res;
    }
};

1.2 二叉树的中序遍历

二叉树先序遍历的过程为：中序序遍历左子树，遍历根结点，中序遍历右子树。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode* root, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        if (root->left != nullptr) {
            inorder(root->left, res);
        }

        res.emplace_back(root->val);

        if (root->right != nullptr) {
            inorder(root->right, res);
        }
    }
};

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == NULL) {
            return res;
        }

        stack<TreeNode*> stk;
        TreeNode* top = root;
        while (!stk.empty() || top) {
            while (top) {
                stk.push(top);
                top = top->left;
            }
            top = stk.top();
            res.push_back(top->val);
            stk.pop();
            top = top->right;
        }
        return res;
    }
};

1.3 二叉树的后序遍历

二叉树先序遍历的过程为：中序序遍历左子树，遍历根结点，中序遍历右子树。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

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

  1. 方法1：传统方法+访问标记
 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
31
32
33

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<pair<TreeNode*, bool>> stk;
        TreeNode* top = root;
        while (!stk.empty() || top) {
            while (top) {
                auto new_node = std::make_pair(top, false);
                stk.push(new_node);
                top = top->left;
            }

            pair<TreeNode*, bool> head = stk.top();
            stk.pop();

            TreeNode* node = head.first;
            int sign = head.second;
            if (sign == false) {
                head.second = true;
                stk.push(head);
                top = node->right;
            } else {
                res.push_back(node->val);
                top = nullptr;
            }
        }
        return res;
    }
};
  1. 方法2：使用两个栈
    该方法类似于先序遍历的非递归方式中的方法2。
    只是为了得到中-右-左的序列，因此是先让左孩子入栈，再让右孩子入栈。
    最终的得到的序列和目标序列顺序相反，在使用一个栈将顺序调整过来即可。
 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
31

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode*> stk;
        stack<TreeNode*> stk_sec;
        stk.push(root);
        while (!stk.empty()) {
            TreeNode* top = stk.top();
            stk.pop();
            stk_sec.push(top);
            if (top->left) {
                stk.push(top->left);
            }
            if (top->right) {
                stk.push(top->right);
            }
        }

        while (!stk_sec.empty()) {
            TreeNode* top = stk_sec.top();
            res.push_back(top->val);
            stk_sec.pop();
        }

        return res;
    }
};
  1. 方法3：使用一个栈
    原理同方法2：但是是通过特殊的先序遍历(遍历的方式为中-右-左的方式)的方式得到中-右-左的序列。 然后将得到的序列翻转一下即可。
 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> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode*> stk;
        TreeNode* top = root;
        while (!stk.empty() || top) {
            while (top) {
                res.push_back(top->val);
                stk.push(top);
                top = top->right;
            }
            top = stk.top();
            stk.pop();

            top = top->left;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

1.4 二叉树的层次遍历

二叉树的层次遍历实际上是对二叉树的广度优先遍历。
原理参考BFS原理的讲解。具体代码实现如下：

 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

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == NULL) {
            return res;
        }
        queue<TreeNode*> que_level;
        que_level.push(root);
        while (!que_level.empty()) {
            int que_size = que_level.size();
            vector<int> level_vec;
            for (int i = 0; i < que_size; ++i) {
                TreeNode* head = que_level.front();
                if (head->left) {
                    que_level.push(head->left);
                }
                if (head->right) {
                    que_level.push(head->right);
                }
                level_vec.push_back(head->val);
                que_level.pop();
            }
            res.push_back(level_vec);
            level_vec.clear();
        }
        return res;
    }
};

2 二叉树的遍历方法总结

二叉树的前序中序、后序遍历都属于深度优先遍历(DFS)，而层次遍历属于广度优先遍历(BFS)。
深度优先遍历需要使用栈作为存储中间过程的数据结构，而广度优先遍历需要使用队列作为中间过程的数据结构。 通过1.1,1.2,1.3的递归实现和非递归实现，我们不难发现。

  1. 三种递归遍历方式实现代码较为简洁，三种遍历的方式的差异在于访问根结点的时机。迭代是访问根结点的时机和对应的遍历方式对应。

  2. 三种非递归方式的实现都有可以使用传统遍历框架，区别在于访问结点的差异：

    • 先序遍历：先访问结点，再放入栈；
    • 中序遍历：先放入栈，出栈时再访问结点；
    • 后序遍历：增加标记，结点进栈两次，第二次出栈时再访问结点；

  3. 先序遍历和后续遍历：可以通过栈后进先出的特性调整顺序，简化操作。