F_JustWei's Studio.

二叉树的遍历

字数统计: 461阅读时长: 2 min
2021/04/05 Share

二叉树的遍历

递归解法

前序遍历

1
2
3
4
5
6
7
8
9
void preorder(TreeNode* root, vector<int>& ans) {
    if (root == nullptr) {
        return;
    }

    ans.emplace_back(root->val);
    preorder(root->left, ans);
    preorder(root->right, ans);
}

中序遍历

1
2
3
4
5
6
7
8
9
void inorder(TreeNode* root, vector<int>& ans) {
    if (root == nullptr) {
        return;
    }

    inorder(root->left, ans);
    ans.emplace_back(root->val);
    inorder(root->right, ans);
}

后序遍历

1
2
3
4
5
6
7
8
9
void postorder(TreeNode* root, vector<int>& ans) {
    if (root == nullptr) {
        return;
    }

    postorder(root->left, ans);
    postorder(root->right, ans);
    ans.emplace_back(root->val);
}

迭代解法

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    if (root == nullptr) {
        return ans;
    }

    stack<TreeNode*> s;
    TreeNode* node = root;
    while (!s.empty() || node != nullptr) {
        while (node != nullptr) {
            ans.emplace_back(node->val);
            s.emplace(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        node = node->right;
    }

    return ans;
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    if (root == nullptr) {
        return ans;
    }

    stack<TreeNode*> s;
    TreeNode* node = root;
    while (!s.empty() || node != nullptr) {
        while (node != nullptr) {
            s.emplace(node);
            node = node->left;
        }

        node = s.top();
        s.pop();
        ans.emplace_back(node->val);
        node = node->right;
    }

    return ans;
}

后序遍历

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

    stack<TreeNode*> s;
    TreeNode* node = root;
    TreeNode* prenode = nullptr;
    while (!s.empty() || node != nullptr) {
        while (node != nullptr) {
            s.emplace(node);
            node = node->left;
        }

        node = s.top();
        s.pop();
        if (node->right == nullptr || node->right == prenode) {
            ans.emplace_back(node->val);
            prenode = node;
            node = nullptr;
        }
        else {
            s.emplace(node);
            node = node->right;
        }
    }

    return ans;
}

层序遍历

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

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    if (root == nullptr) {
        return ans;
    }

    queue<TreeNode*> q;
    q.emplace(root);
    while (!q.empty()) {
        int cnt = q.size();
        vector<int> t;

        for (int i = 0; i < cnt; i++) {
            TreeNode* node = q.front();
            q.pop();
            t.emplace_back(node->val);
            if (node->left) {
                q.emplace(node->left);
            }
            if (node->right) {
                q.emplace(node->right);
            }
        }
        ans.emplace_back(t);
    }

    return ans;
}

暂时没有Morris 遍历

原文作者：F_JustWei

原文链接：http://139.196.79.90/2021/04/05/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86/

发表日期：April 5th 2021, 4:57:24 pm

更新日期：April 22nd 2021, 12:24:56 am

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 二叉树的遍历
    1. 1.0.1. 递归解法
      1. 1.0.1.1. 前序遍历
      2. 1.0.1.2. 中序遍历
      3. 1.0.1.3. 后序遍历
    2. 1.0.2. 迭代解法
      1. 1.0.2.1. 前序遍历
      2. 1.0.2.2. 中序遍历
      3. 1.0.2.3. 后序遍历
      4. 1.0.2.4. 层序遍历
Total : 130
2021
2019
leetcode 动态规划 字符串 树 数据结构 C++ STL algorithm 容器 操作系统 软考 Java PTA 计算机网络 UML 迭代器 C JSON 信息安全 模板 多媒体， 软考 数据库 软件工程 排序 Spring 人机交互