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

N 叉树 定义

• 二叉树是一颗以根节点开始，每个节含有不超过2个子节点的树。N 叉树，即每个节点不超过N个子节点的树。
• 一颗三叉树：

遍历

N-ary Tree Preorder Traversal:

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

例如，给定一个 3叉树 :

说明: 递归法很简单，你可以使用迭代法完成此题吗?

• 方法一：递归法：

class Solution {public:	vector
   
     preorder(Node* root){		if(root != nullptr)		{			res.push_back(root->val);			for(auto n :  root->children)				preorder(n);		}		return res;	}private:	vector
    
      res;};
    
   

• 方法二：迭代法： 用栈

/*// Definition for a Node.class Node {public:    int val;    vector
   
     children;    Node() {}    Node(int _val, vector
    
      _children) {        val = _val;        children = _children;    }};*/class Solution {public:    vector
     
       preorder(Node* root) {        if(root == nullptr)            return res;                s_node.push(root);        while(!s_node.empty())        {            Node* temp = s_node.top();            res.push_back(temp->val);            s_node.pop();            for(int i = temp->children.size() - 1; i>=0; i--)            {                s_node.push(temp->children[i]);            }        }        return res;    }private:    vector
      
        res;    stack
       
         s_node;    };
       
      
     
    
   

N-ary Tree Postorder Traversal

• 方法 1 ：递归法

class Solution {public:    vector
   
     postorder(Node* root) {        if(root != nullptr){            for(auto n : root->children)            {                postorder(n);                         }            res.push_back(root->val);          }        return res;    }private:    vector
    
      res;};
    
   

方法二：迭代 ：栈

• 我们同样使用迭代先把根节点放入栈中，然后把它的孩子依次放入，这样我们下次遍历获得的就是它的最后的节点，每层都是如此。我们每层都是根->右孩子->其余孩子的遍历方式，所以最后需要加一个翻转即可得到后序遍历。

/*// Definition for a Node.class Node {public:    int val;    vector
   
     children;    Node() {}    Node(int _val, vector
    
      _children) {        val = _val;        children = _children;    }};*/class Solution {public:    vector
     
       postorder(Node* root) {        if(root)        {            s_node.push(root);            while(!s_node.empty())            {                Node* temp = s_node.top();                s_node.pop();                res.push_back(temp->val);                             for(auto x : temp->children)                {                    s_node.push(x);                }            }                      int size = res.size();                    for(int i=0; i < size/2; i++)            {                int buf = res[i];                res[i]  = res[size - i - 1];                res[size - i - 1] = buf;            }        }        return res;    }private:    vector
      
        res;    stack
       
         s_node;};
       
      
     
    
   

N叉树的层序遍历

• 思路， 首先想到用队列；
• 每一层的个数得知道吧？
• 每一层分别遍历不就可以了
• 一层一层的进入队列这是关键，不然分界点怎么办，于是先求首层的（root）的大小，遍历此层并出队列，加入结果中，然后将此层的结点放进队列中； 第二次求 第二层的大小，然后遍历并出队列，然后将第三层结点放进队列！！！

/*// Definition for a Node.class Node {public:    int val = NULL;    vector
   
     children;    Node() {}    Node(int _val, vector
    
      _children) {        val = _val;        children = _children;    }};*/class Solution {public:    vector
     
      
       > levelOrder(Node* root) {        if(root)        {            q_node.push(root);                 while(!q_node.empty())            {                int size = q_node.size();                vector
       
         r(size);                for(int i = 0; i < size; i++)                {                     Node* temp = q_node.front();                     q_node.pop();                     r[i] = temp->val;                     for(auto x : temp->children)                     {                         q_node.push(x);                     }                }                 res.push_back(r);            }                    }        return res;    }    private:    vector
        
         
          > res; queue
          
            q_node;};
          
         
        
       
      
     
    
   

Maximum Depth of N-ary Tree

• 递归！！！

对于二叉树来说求一棵树的最大深度！

int maxDepth(ThreeNode* node){	if(node == nullptr)		return  0 ;	return max(maxDepth(node->left), maxDepth(node->right)) + 1;}

• 扩展到多叉树，所以是对所有孩子结点进行判断！

/*// Definition for a Node.class Node {public:    int val;    vector
   
     children;    Node() {}    Node(int _val, vector
    
      _children) {        val = _val;        children = _children;    }};*/class Solution {public:    int maxDepth(Node* root) {        if(root == nullptr)            return 0;        int dep = 0;        for(auto x : root->children)            dep = max(dep, maxDepth(x));        return dep+1;    }};
    
   

下面的方法可能更能懂，root 不为空 则 dep 至少 为 1，有孩子则深度 加 +1.

class Solution {public:    int maxDepth(Node* root) {        if(root == nullptr)            return 0;        int dep = 1;        for(auto x : root->children)            dep = max(dep, maxDepth(x) + 1);        return dep;    }};

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