N叉树操作

589. N 叉树的前序遍历

• 先操作根节点，再递归操作根节点的子节点

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> res;
    void dfs(Node* root){        
        if (root == nullptr) return; // 递归结束的条件
        res.push_back(root->val);  // 记录当前根节点
        for (auto& child : root->children){  // 对各个子节点进行遍历
            dfs(child);
        }
    }
    vector<int> preorder(Node* root) {
        dfs(root);
        return res;
    }
};

590. N 叉树的后序遍历

• 先递归操作根节点的子节点，再操作根节点

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> res;
    void dfs(Node* root){        
        if (root == nullptr) return; // 递归结束的条件

        for (auto& child : root->children){  // 对各个子节点进行遍历
            dfs(child);
        }
        res.push_back(root->val);  // 记录当前根节点
    }
    vector<int> postorder(Node* root) {
        dfs(root);
        return res;

    }
};

429. N 叉树的层序遍历

• 用一个队列记录层序遍历的过程
• 记录当前层的队列大小，当前层中每有一个节点出队，就把这个节点对应的子节点入队

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector <vector<int>> levelOrder(Node *root) {
        if (root == NULL) return {}; // 若为空，则返回{}
        vector <vector<int>> res; // 保存全局结果
        queue < Node * > q; // 用队列记录遍历过程
        q.push(root); // 先把当前根节点入队
        while (!q.empty()) {
            int n=q.size(); // 记录这批次的队列长度
            vector<int> tmp; // 保存每一层的数据
            for (int i = 0; i < n;  ++i) {
                Node *curRoot = q.front(); // 取到当前队头
                tmp.push_back(curRoot->val); // 把当前队头的值保存在tmp中
                q.pop(); // 队头出队
                for (auto &child : curRoot->children){
                    q.push(child); // 每出一个当前队头，就把当前队头的子节点入队
                }
            }
            res.push_back(tmp); // 把这层的数据保存在res中
        }
        return res;
    }
};

559. N 叉树的最大深度

找到子树的最大深度，然后+1 （因为当前节点也占一个深度）

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        if (root== nullptr) return 0;  // 递归结束的条件
        int res=0; // 保存子节点的最大深度
        for(auto &child:root->children){
            res=max(maxDepth(child),res);
        }
        return res+1; // 因为当前节点也占一个深度，所以子节点的最大深度+1
    }
};