本文共 2605 字，大约阅读时间需要 8 分钟。

c/c++ leetcode N叉树的前后遍历

前序遍历

题目描述

难度简单91

给定一个 N 叉树，返回其节点值的前序遍历。

例如，给定一个 3叉树 :

返回其前序遍历: [1,3,5,6,2,4]。

解法一: 递归

前序遍历的访问顺序:

根节点 -> 左子树 -> 右子树;

需要注意的是这返回的结果不能局部的变量 ,也不可以是值传递;

class Solution {public:    vector
   
     preorder2(Node* root) {        vector
    
      temp;        if (root == NULL) return temp;                return DLR(root,temp);            }private:    //DLR - 是前序遍历    vector
     
       DLR(Node* root,vector
      
       & temp);};vector
       
         Solution::DLR(Node* root,vector
        
         & temp){ if(root == NULL) return temp; temp.push_back(root -> val); int len = root -> children.size(); for(int i = 0; i
         
           children[i],temp); } return temp;}
         
        
       
      
     
    
   

时空复杂度分析:

时间复杂度:为O(N); N是树的节点个数

空间复杂度: 为 O(N); 开辟的栈空间;

解法二:用stack容器

vector
   
     preorder(Node* root) {        vector
    
      ret;        stack
     
       S;        Node* temp = NULL;        if(root == NULL) return ret;        S.push(root);        while(!S.empty()){            temp = S.top();            S.pop();            ret.push_back(temp -> val);			            //逆向遍历孩子数组,让最右孩子先进栈             for(vector
      
       ::reverse_iterator it =temp -> children.rbegin();                  it != temp -> children.rend();it++){                 S.push(*it);            }        }        return ret;            }
      
     
    
   

后序遍历

题目描述

难度简单89收藏分享切换为英文关注反馈

给定一个 N 叉树，返回其节点值的后序遍历。

例如，给定一个 3叉树 :

返回其后序遍历: [5,6,3,2,4,1].

解法一: 递归

前序遍历的访问顺序:

左子树 -> 右子树 -> 根节点;

class Solution {public:    vector
   
     postorder(Node* root) {        if (root == NULL) return ans;                for (int i = 0; i < root -> children.size(); ++i){            postorder(root -> children[i]) ;        }        ans.push_back(root -> val);                return ans;    }private:    vector
    
      ans;};
    
   

时空复杂度分析:

时间复杂度:为O(N); N是树的节点个数

空间复杂度: 为 O(N); 开辟的栈空间;

解法二:用stack容器

也就是前序遍历,只不过是使用的deque容器的push_front() 方法每次在第一个元素插入 遍历结束后再把元素赋值给vector容器.

class Solution {public:    vector
   
     postorder(Node* root) {        stack
    
      s;        deque
     
       ans;        if (!root) return vector
      
       ();        s.push(root);        while (!s.empty() ) {           Node * temp = s.top();           s.pop();           ans.push_front(temp -> val);            //正向遍历 孩子数组;让最左孩子先进栈           for (auto loop : temp -> children) {               s.push(loop);           }        }        vector 
       
         ret(ans.begin(),ans.end());        return ret;    }};
       
      
     
    
   

时空复杂度分析:

时间复杂度:为O(N); N是树的节点个数,每个节点只会入栈和出栈各一次。

空间复杂度: 使用了三个容器来存储节点或节点数据为O(3N) 去掉项数 为O(N);

转载地址：http://kdyki.baihongyu.com/