首页

二叉树的遍历方式

假定二叉树的节点的定义如下：

1
2
3
4
5
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
}

对节点的数据的访问通过调用visit()实现，例如当要把节点的数据按照遍历顺序加入一个向量nums中，可以将visit(x)改为nums.push_back(x)。

1 二叉树的广度优先遍历（层次遍历）

广度优先遍历可以用队列来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
void levelTraversal(TreeNode* root)
{
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        TreeNode* temp = q.pop();
        visit(temp ->val);
        if(temp ->left)
            q.push(x->left);
        if(temp ->right)
            q.push(x->right);
    }
}

2 二叉树的深度优先遍历

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
24
25
26
27
//前序遍历
void preTrav(TreeNode* root)
{
    if(!root)
        return;
    visit(x->val);
    preTrav(root->left);
    preTrav(root->right);
}
//中序遍历
void inTrav(TreeNode* root)
{
    if(!root)
        return;
    inTrav(root->left);
    visit(x->val);
    inTrav(root->right);
}
//后序遍历
void postTrav(TreeNode* root)
{
    if(!root)
        return;
    postTrav(root->left);
    postTrav(root->right);
    visit(x->val);
}

2.2 非递归算法

2.2.1 非递归算法实现1

参考来源：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/
（遍历过程可以认为每个节点都将被访问两次。当访问到一个节点时，如果是第一次访问，将这个节点、这个节点的非空左右节点加入栈（入栈的顺序根据访问顺序调整），如果是第二次访问，说明是回溯到了这个节点，此时调用visit()函数访问这个节点的数据）

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//前序遍历
void preTrav(TreeNode* root)
{
    stack<pair<bool, TreeNode*>> stk;
    if(root)
    	stk.push(pair<bool, TreeNode*>(false, root));
    while(!stk.empty()){
        pair<bool, TreeNode*> temp = stk.top();
        stk.pop();
        if(temp.first){//true表示是第二次访问到这个节点
            visit(temp.second->val);
        }
        else{//false表示第一次访问到这个节点
        //前序、中序和后序遍历的代码只有下面部分不同
            if(temp.second->right) 
                stk.push(pair<bool, TreeNode*>(false, temp.second->right));
            if(temp.second->left)
                stk.push(pair<bool, TreeNode*>(false, temp.second->left));
            stk.push(pair<bool, TreeNode*>(true, temp.second));
        }
    }
}
//中序遍历
void inTrav(TreeNode* root)
{
    stack<pair<bool, TreeNode*>> stk;
    if(root)
    	stk.push(pair<bool, TreeNode*>(false, root));
    while(!stk.empty()){
        pair<bool, TreeNode*> temp = stk.top();
        stk.pop();
        if(temp.first){
            visit(temp.second->val);
        }
        else{
            if(temp.second->right) 
                stk.push(pair<bool, TreeNode*>(false, temp.second->right));
            stk.push(pair<bool, TreeNode*>(true, temp.second));
            if(temp.second->left)
                stk.push(pair<bool, TreeNode*>(false, temp.second->left));
        }
    }
    return;
}
//后序遍历
void postTrav(TreeNode* root)
{
    stack<pair<bool, TreeNode*>> stk;
    if(root)
    	stk.push(pair<bool, TreeNode*>(false, root));
    while(!stk.empty()){
        pair<bool, TreeNode*> temp = stk.top();
        stk.pop();
        if(temp.first){
            visit(temp.second->val);
        }
        else{
            stk.push(pair<bool, TreeNode*>(true, temp.second));
            if(temp.second->right) 
                stk.push(pair<bool, TreeNode*>(false, temp.second->right));
            if(temp.second->left)
                stk.push(pair<bool, TreeNode*>(false, temp.second->left));
        }
    }
}

2.2.2 非递归算法实现2

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void preTrav(TreeNode* root)
{
    stack<TreeNode*> stk; 
    if(root) 
        stk.push(root);
    while(!stk.empty()){
        TreeNode* temp = stk.top();
        stk.pop();
        visit(temp->val);
        if(temp->right)
            stk.push(temp->right);
        if(temp->left)
            stk.push(temp->left);
    }
}

另外一种写法：

对于任意一个结点node，具体步骤如下：

a)访问之，并把结点node入栈，当前结点置为左孩子；

b)判断结点node是否为空，若为空，则取出栈顶结点并出栈，将右孩子置为当前结点；否则重复a)步直到当前结点为空或者栈为空（可以发现栈中的结点就是为了访问右孩子才存储的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void preOrderTraverse2(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode pNode = root;
    while (pNode != null || !stack.isEmpty()) {
        if (pNode != null) {
            visit(pNode.val);
            stack.push(pNode);
            pNode = pNode.left;
        } else { //pNode == null && !stack.isEmpty()
            TreeNode node = stack.pop();
            pNode = node.right;
        }
    }
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void inTrav(TreeNode* root)
{
    stack<TreeNode*> stk;
    TreeNode* node = root;
    while (!stk.empty() || node) {
        while (node) {//沿着左子树遍历
            stk.emplace(node);
            node = node->left;
        }
        if(!stk.isEmpty()){
            node = stk.top();
            stk.pop();
            visit(node->val);
            node = node->right;
        }
    }
}

另外一种写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void inOrderTraverse2(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode pNode = root;
    while (pNode != null || !stack.isEmpty()) {
        if (pNode != null) {
            stack.push(pNode);
            pNode = pNode.left;
        } else { //pNode == null && !stack.isEmpty()
            TreeNode node = stack.pop();
            visit(node.val);
            pNode = node.right;  // 访问右节点和右节点的子树
        }
    }
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void postTrav(TreeNode* root)
{
    stack<TreeNode*> stk;
    TreeNode *prev = NULL;
    TreeNode *node = root;
    while(node || !stk.empty()) {
        while(node) { //沿着左子树遍历
            stk.emplace(node);
            node = node->left;
        }
        node = stk.top();
        stk.pop();
        if(!node->right || node->right == prev) {//右子树为空或者上一个刚访问过的节点
            visit(node->val);
            prev = node;
            node = NULL;
        } 
        else{//继续沿着右子树遍历
            stk.emplace(node);
            node = node->right;
        }
    }
}

另外一种方式：

image-20230826194715256

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        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;
    }
};

2.2.3 非递归实现算法3

这也是一种统一的非递归迭代算法，这种方法和2.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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    if (root != NULL) st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        if (node != NULL) {
            st.pop();
            if (node->right) st.push(node->right);  // 右
            if (node->left) st.push(node->left);    // 左
            st.push(node);                          // 中
            st.push(NULL);
        } else {
            st.pop();
            node = st.top();
            st.pop();
            result.push_back(node->val);
        }
    }
    return result;
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    if (root != NULL) st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        if (node != NULL) {
            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            if (node->right) st.push(node->right);  // 添加右节点（空节点不入栈）

            st.push(node);                          // 添加中节点
            st.push(NULL); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            if (node->left) st.push(node->left);    // 添加左节点（空节点不入栈）
        } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
            st.pop();           // 将空节点弹出
            node = st.top();    // 重新取出栈中元素
            st.pop();
            result.push_back(node->val); // 加入到结果集
        }
    }
    return result;
}


vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    if (root != NULL) st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        if (node != NULL) {
            st.pop();
            st.push(node);                          // 中
            st.push(NULL);

            if (node->right) st.push(node->right);  // 右
            if (node->left) st.push(node->left);    // 左

        } else {
            st.pop();
            node = st.top();
            st.pop();
            result.push_back(node->val);
        }
    }
    return result;
}