二叉树遍历

概述

  • 二叉树是一种经常用到的数据结构，用来模拟具有树状结构性质的数据集合。

  • 二叉树是一种更为典型的树状结构。如它名字所描述的那样，二叉树是每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”。

定义二叉树的节点

1
2
3
4
5
6
7
8
9
10
//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr),right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode right) : val(x), left(left), right(right) {}
};

常见的二叉树遍历方式有前序遍历、中序遍历、后序遍历、层序遍历。下面实现二叉树遍历的四种方式：

遍历方式

前序遍历

前序遍历的顺序是 根节点->左节点->右节点

下列二叉树的前序遍历为： A B D E C F

image-20211009130611162

递归实现

利用递归实现前序遍历十分简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> preorderTraversal(TreeNode* root){
    vector<int> ans;
    
    dfs(root, ans);
    return ans;
}

void dfs(TreeNode* root, vector<int> ans){
    if(root == nullptr){
        return;
    }
    
    ans.push_back(root->val);
    dfs(root->left);
    dfs(root->right);
}

栈实现方法

利用栈实现前序遍历的核心是将树节点push到栈中然后在合适的时间从栈中弹出。

  • 首先将左节点push到栈中，push的同时访问当前节点数据。直到当前节点的左节点为nullptr。
  • 判断栈是否为空，如果不为空就弹出当前栈顶节点，并push栈顶节点的右节点。
  • 迭代上述操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> preorderTraversal(TreeNode* root) {
    stack<TreeNode *> mySta;
    vector<int> ans;
    TreeNode* cur = root;
    while(cur != nullptr || !mySta.empty()){
        while(cur != nullptr){
            mySta.push(cur);
            ans.push_back(cur->val);
            // mySta.push(cur);
            cur = cur->left;
        }

        if(!mySta.empty()){
            cur = mySta.top();
            mySta.pop();
            cur = cur->right;
        }
    }
    return ans;
}

中序遍历

中序遍历的顺序是 左节点->根节点->右节点

下列二叉树的中序遍历为： D B E A F C

image-20211009135839077

递归实现

利用递归实现中序遍历十分简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> inorderTraversal(TreeNode* root){
    vector<int> ans;
    
    dfs(root, ans);
    return ans;
}

void dfs(TreeNode* root, vector<int> ans){
    if(root == nullptr){
        return;
    }
    
    dfs(root->left);
    ans.push_back(root->val);
    dfs(root->right);
}

栈实现方法

利用栈实现中序遍历的核心与前序遍历相同，只是需要注意访问节点数据的时机有所不同。

  • 首先将左节点push到栈中直到当前节点的左节点为nullptr。
  • 判断栈是否为空，如果不为空就访问当前栈顶节点，并弹出当前栈顶节点，并push栈顶节点的右节点。
  • 迭代上述操作。
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) {
        vector<int> ans;
        stack<TreeNode*> mySta;
        // mySta.push(root);

        TreeNode *cur = root;
        while(cur != nullptr || !mySta.empty()){
            while(cur != nullptr){
                mySta.push(cur);
                cur = cur->left;
            }

            if(!mySta.empty()){
                cur = mySta.top();
                mySta.pop();
                ans.push_back(cur->val);
                cur = cur->right;
            }
        }
        return ans;
    }

后序遍历

后序遍历的顺序是 左节点->右节点->根节点

下列二叉树的后序遍历为： D E B F C A

image-20211009140543901

递归实现

利用递归实现前序遍历十分简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> postorderTraversal(TreeNode* root){
    vector<int> ans;
    
    dfs(root, ans);
    return ans;
}

void dfs(TreeNode* root, vector<int> ans){
    if(root == nullptr){
        return;
    }
    
    dfs(root->left);
    dfs(root->right);
    ans.push_back(root->val);
}

栈实现方法

利用栈实现二叉树的后序遍历的核心与前序遍历相同。但需要注意的是，如果直接使用栈来实现后序遍历会相对比较麻烦，因为需要控制第二次访问根节点才能将栈顶元素弹出，从而需要一个额外的栈来实现节点的访问计数。因此我将讨论后序遍历与前序遍历之间的关系，来寻找更加简便的方法。

根据前面的讨论我们可以得知

  • 前序遍历访问节点的顺序是 根节点->左节点->右节点
  • 后序遍历访问节点的顺序是 左节点->右节点->根节点

假设我们将前序遍历的左右节点访问顺序交换，我们将会得到 根节点->右节点->左节点 的访问顺序。

接着将上述的顺序进行reverse。得到的顺序是 左节点->右节点->根节点 恰好和后序遍历的顺序相同。

因此我们只需要将前序遍历的栈实现方式中的所有左节点改为右节点，右节点改为左节点。同时在最后对结果进行reverse即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode *> mySta;
    vector<int> ans;
    TreeNode* cur = root;
    while(cur != nullptr || !mySta.empty()){
        while(cur != nullptr){
            mySta.push(cur);
            ans.push_back(cur->val);
            // mySta.push(cur);
            cur = cur->right;
        }

        if(!mySta.empty()){
            cur = mySta.top();
            mySta.pop();
            cur = cur->left;
        }
    }
    reverse(ans.begin(),ans.end());
    return ans;

}

层序遍历

层序遍历就是逐层遍历树结构。

广度优先搜索是一种广泛运用在树或图这类数据结构中，遍历或搜索的算法。 该算法从一个根节点开始，首先访问节点本身。 然后遍历它的相邻节点，其次遍历它的二级邻节点、三级邻节点，以此类推。

当我们在树中进行广度优先搜索时，我们访问的节点的顺序是按照层序遍历顺序的。

下列二叉树的后序遍历为：A B C D E F

image-20211009142500875

广度优先搜索实现

广度优先搜索的核心是队列。将队首元素出队，如果该节点有子节点则将子节点入队。直到队首节点没有子节点，并且队列中没有节点时，遍历结束。

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
vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> myQueue;
    vector<vector<int>> ans;
    if(root == nullptr){
        return ans;
    }

    myQueue.push(root);
    while(!myQueue.empty()){
        int cnt = myQueue.size();
        vector<int> temp;
        for(int i = 0; i<cnt; i++){
            TreeNode *cur = myQueue.front();
            myQueue.pop();
            temp.push_back(cur->val);

            if(cur->left != nullptr){
                myQueue.push(cur->left);
            }
            if(cur->right != nullptr){
                myQueue.push(cur->right);
            }
        }
        ans.push_back(temp);
    }
    return ans;

}