0xzhang的博客

树的遍历

· 0xzhang

N叉树的遍历§

前序§

递归版

对于N叉树的前序遍历,首先读取数值,然后从左向右依次对所有孩子结点进行递归调用。

class Solution {
public:
    void rec(Node* root, vector<int>& vpre){
        if(!root) return;
        vpre.emplace_back(root->val);
        for(Node* p:root->children){
            rec(p,vpre);
        }
    }

    vector<int> preorder(Node* root){
        vector<int> ans;
        if(!root) return ans;
        rec(root,ans);
        return ans;
    }
};

非递归

前序遍历的非递归方法需要借助栈。首先根结点入栈,然后进入循环,只要栈非空,访问栈顶结点并从右向左将其所有孩子结点逆序入栈,继续循环。

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans;
        stack<Node*> ts;
        if(root) ts.push(root);
        while(!ts.empty()){
            Node* p=ts.top();
            ans.push_back(p->val);
            ts.pop();
            for(auto t=p->children.crbegin();t!=p->children.crend();++t){
                ts.push(*t);
            }
        }
        return ans;
    }
};

后序§

递归版

先递归,再取数(值)。

class Solution {
public:
    void rec(Node* root, vector<int> &vpost){
        if(!root) return;
        for(Node* p:root->children)
            rec(p,vpost);
        vpost.emplace_back(root->val); 
    }

    vector<int> postorder(Node* root){
        vector<int> ans;
        if(!root) return ans;
        rec(root,ans);
        return ans;
    }
};

非递归

这是一个有技巧的方法,先记录下来。首先根结点入栈,然后进入循环,只要栈非空,读取栈顶结点数值并从左向右依次将孩子结点入栈。这样的结果是,对任意子树,总是先获得根结点数值,再从右向左获得所有孩子结的值。因此反转获得的数值序列得到后序遍历结果。

class Solution {
public:
	vector<int> postorder(Node* root){
        vector<int> ans;
        if(!root) return ans;
        stack<Node*> ts;
        ts.push(root);
        while(!ts.empty()){
            Node* p=ts.top();
            ans.emplace_back(p->val);
            ts.pop();
            for(Node* t:p->children){
                ts.push(t);
            }
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

层序§

层序遍历需要借助队列实现。根结点入队后进入循环,首先取当前队列大小,表示一层中结点数,依次取数据并将所有孩子结点入队。

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        queue<Node*> q;
        q.push(root);

        while(!q.empty()){
            int cnt=q.size();
            vector<int> rec;
            for(int i=0;i<cnt;++i){
                Node* cur=q.front();
                q.pop();
                rec.emplace_back(cur->val);
                for(Node* t:cur->children)
                    q.emplace(t);
            }
            ans.emplace_back(rec);
        }
        return ans;
    }
};

二叉树的中序遍历§

递归版

class Solution {
public:
    void rec(Node* root, vector<int> &vin){
        if(!root) return;
        rec(root->left,vin);
        vin.emplace_back(root->val); 
        rec(root->right,vin);
    }

    vector<int> inorder(Node* root){
        vector<int> ans;
        if(!root) return ans;
        rec(root,ans);
        return ans;
    }
};

非递归

两种方法。

第一种,首先迭代将左孩子入栈直到没有左孩子为止,然后进入循环,只要栈非空,取栈顶数据并出栈,每当结点有右孩子时,右孩子入栈并迭代将左孩子入栈。

第二种,以根结点为当前结点,只要栈非空或当前结点存在进行循环,循环中有两部分,第一部分迭代将当前结点的左孩子入栈,第二部分取栈顶数据并出栈,使得当前结点为栈顶结点的右孩子(无论右孩子是否存在)。

class Solution {
public:
    vector<int> inorderTraversal1(TreeNode* root) {
        vector<int> ans; 
        if(!root) return ans;
        stack<TreeNode*> ts;
        ts.push(root);
        while(root->left){
            root=root->left;
            ts.push(root);
        }
        while(!ts.empty()){
            TreeNode* cur=ts.top();
            ans.emplace_back(cur->val);
            ts.pop();
            if(cur->right){
                TreeNode* t=cur->right;
                ts.push(t);
                while(t->left){
                    t=t->left;
                    ts.push(t);
                }
            }
        }
        return ans;
    }
    
    vector<int> inorderTraversal2(TreeNode* root) {
        vector<int> ans; 
        stack<TreeNode*> ts;
        TreeNode* cur=root;
        while(!ts.empty()||cur){
            while(cur){
                ts.push(cur);
                cur=cur->left;
            }
            if(!ts.empty()){
                cur=ts.top();
                ans.emplace_back(cur->val);
                ts.pop();
                cur=cur->right;
            }
        }
        return ans;
    }
};

参考资料§

[1] 二叉树的遍历(前、中、后序及层次遍历,递归和非递归实现) - 何大土 - 博客园