二叉树的遍历方法总结

二叉树的遍历方法总结

二叉树的遍历有前序遍历，中序遍历，后续遍历和层序遍历，这几种方法都可以通过递归和循环来实现。

二叉树数据结构定义

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

二叉树的前序遍历

  • 递归实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            if(!root){
                return {};
            }
            vector<int> res;
            preorderTraversal(root,res);
            return res;
        }
        void preorderTraversal(TreeNode* root, vector<int>& res){
            if(!root){
                return;
            }
            res.push_back(root->val);
            preorderTraversal(root->left,res);
            preorderTraversal(root->right,res);
            return;
        }
    };

  • 循环实现

    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> preorderTraversal(TreeNode* root) {
            if(!root){
                return {};
            }
            vector<int> res;
            stack<TreeNode*> nodes;
            nodes.push(root);
            while(!nodes.empty()){
                TreeNode* node = nodes.top();
                nodes.pop();
                res.push_back(node->val);
                if(node->right){
                    nodes.push(node->right);
                }
                if(node->left){
                    nodes.push(node->left);
                }
            }
            return res;
        }
    };

二叉树的中序遍历

  • 递归实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            if(!root) return{};
            vector<int> res;
            inorderTraversal(root,res);
            return res;
        }
        void inorderTraversal(TreeNode* root, vector<int>& res){
            if(!root){
                return;
            }
            inorderTraversal(root->left, res);
            res.push_back(root->val);
            inorderTraversal(root->right,res);
        }
    };

  • 循环实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            stack<TreeNode*> s;
            vector<int> res;
            TreeNode* r = root;
            while(!s.empty() || r!=NULL){
                while(r!=NULL){
                    s.push(r);
                    r = r->left;
                }
                r = s.top();
                s.pop();
                res.push_back(r->val);
                r=r->right;
            }
            return res;
        }
    };

二叉树的后序遍历

  • 递归实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> res;
            if(!root) return {};
            postorderTraversal(root,res);
            return res;
        }
        void postorderTraversal(TreeNode* root, vector<int>& res){
            if(!root){
                return;
            }
            postorderTraversal(root->left,res);
            postorderTraversal(root->right,res);
            res.push_back(root->val);
        }
    };

  • 循环实现

    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
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            if(!root) return {};
            stack<TreeNode*> nodes;
            vector<int> res;
            TreeNode* pre = NULL;
            nodes.push(root);
            while(!nodes.empty()){
                TreeNode* node = nodes.top();
                
                if( (node->left==NULL && node->right==NULL) || 
                    (pre!=NULL && (node->left==pre || node->right==pre))){
                    pre = node;
                    res.push_back(node->val);
                    nodes.pop();
                }else{
                    if(node->right){
                        nodes.push(node->right);
                    }
                    if(node->left){
                        nodes.push(node->left);
                    }
                }
            }
            return res;
        }            
    };

二叉树的层序遍历

  • 递归实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            vector<vector<int> > res;
            if(root==NULL) return res;
            levelOrder(root,res,0);
            return res;
        }
        void levelOrder(TreeNode* root, vector<vector<int> >&res, int level){
            if(root==NULL) return;
            if(res.size()==level){
                res.push_back(vector<int>(1,root->val));
            }else{
                res[level].push_back(root->val);
            }
            levelOrder(root->left,res,level+1);
            levelOrder(root->right,res,level+1);
            return;
        }
    };

  • 循环实现

    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) return res;
            queue<TreeNode*> nodes;
            nodes.push(root);
            int level=0;
            while(!nodes.empty()){
                int level_size = nodes.size();
                int count = 0;
                res.push_back(vector<int>(0));
                while(count<level_size){
                    TreeNode* node = nodes.front();
                    nodes.pop();
                    res[level].push_back(node->val);
                    count++;
                    if(node->left){
                        nodes.push(node->left);
                    }
                    if(node->right){
                        nodes.push(node->right);
                    }
                }
                level++;
            }
            return res;
        }
    };
发布于 
tags:
  • { 数据结构 }