算法学习 - 二叉树遍历

• 参考:《labuladong的算法小抄》
• 参考: 二叉树的三种遍历递归与迭代写法

深度优先遍历

二叉树遍历的深度优先遍历可以通过递归和迭代来实现.

递归

递归方法遍历二叉树比较简单, 只要注意处理数据的代码的位置即可.

void traverse(TreeNode* root)
{
    if(root == nullptr) return;
    // 前序遍历代码
    traverse(root->left);
    // 中序遍历代码
    traverse(root->right);
    // 后序遍历代码
}
1
2
3
4
5
6
7
8
9

迭代

二叉树遍历的迭代解法使用栈数据结构来模拟递归调用.

前序遍历

void preorderTraverse(TreeNode* root)
{
    stack<TreeNode*> st;
    st.push(root);
    while(!st.empty())
    {
        int sz = st.size();
        for(int i = 0; i<sz; ++i)
        {
            TreeNode *cur = st.top();
            st.pop();
            if(cur != nullptr)
            {
                //对cur指向的节点的数据进行处理
                //...
                //注意先右后左!!
                if(cur->right != nullptr) st.push(cur->right);
                if(cur->left != nullptr) st.push(cur->left);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

中序遍历

void inorderTraverse(TreeNode* root)
{
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while(cur || !st.empty())
    {
        while(cur)
        {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        //处理当前节点数据
        //...
        cur = cur->right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

后序遍历

void postorderTraverse(TreeNode* root)
{
    stack<TreeNode*> st;
    TreeNode* cur = root;
    TreeNode* prev = nullptr;	//需要记录前置的访问节点
    while(cur || !st.empty())
    {
        //将当前节点和所有的左子树节点压入栈中
        while(cur)
        {
            st.push(cur);
            cur = cur->left;
        }
        //此时cur为null, 弹出栈顶元素
        cur = st.top();
        st.pop();
        //如果当前节点的右子树为空 或 之前访问的节点是自己的右子树 
        if(cur->right == nullptr || prev == cur->right)
        {
            //对数据节点处理
            //...
            prev = cur;
            cur = nullptr;	//注意将当前节点置为空, 否则下轮循环将访问节点的左子树
        }
        else 
        {
            st.push(cur);
            cur = cur->right;
        }
    }
}
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

---

另一种解法:
结点访问的顺序:

• 前序遍历: root->left->right
• 后序遍历: left->right->root

因此使用前序遍历的代码, 我们可以先将左子树入栈, 再将有子树入栈, 这样得到的遍历顺序是: root->right->left, 最后将所得的结果反向即可

vector<int> postorderTraverse_2(TreeNode* root)
{
    vector<int> ret;
    stack<TreeNode*> st;
    st.push(root);
    while(!st.empty())
    {
        int sz = st.size();
        for(int i = 0; i<sz; ++i)
        {
            TreeNode* cur = st.top();
            st.pop();
            if(cur) ret.emplace_back(cur->val);
            if(cur->left) st.emplace(cur->left);
            if(cur->right) st.emplace(cur->right);
        }
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

广度优先遍历

void BFS(TreeNode *root)
{
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        int sz = q.size();
        for(int i = 0; i<sz; ++i)
        {
            TreeNode* cur = q.front();
            q.pop();
            if(cur)
            {
                //对节点数据的操作
                //...
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

节点定义

class TreeNode
{
public:
    TreeNode(){}
    TreeNode(int _val):val(_val){}
    ~TreeNode(){}

    int val;
    TreeNode *left;
    TreeNode *right;
};
1
2
3
4
5
6
7
8
9
10
11