leetcode589.N叉树的前序遍历

题目

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

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

提示：

• 节点总数在范围 [0, 104]内
• 0 <= Node.val <= 104
• n 叉树的高度小于或等于 1000

进阶：递归法很简单，你可以使用迭代法完成此题吗?

解答

• 递归法

/*
// 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> preorder(Node* root) {
        // 结果数组result的定义
        vector<int> result;
        // 如果root为空，则直接返回空数组
        if (!root) return result;
        // 如果root不为空，则开始前序遍历
        preorderHelper(root, result);
        // 遍历结束返回结果数组
        return result;
    }

    void preorderHelper(Node* node, vector<int>& finalResult) {
        if (!node) return; // 递归的终止条件：结点为空
        finalResult.push_back(node->val); // 前序遍历
        for (Node* child: node->children) { // 获取当前结点的子结点
            // 然后分别每一个子结点进行前序遍历
            preorderHelper(child, finalResult); 
        }
    }
};

• 迭代法

/*
// 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> preorder(Node* root) {
        stack<Node*> st; // 使用栈，先进后出
        vector<int> result; // 结果数组的定义
        if (!root) return result;
        st.push(root); // 将根节点入栈
        while (!st.empty()) { // 当栈非空时
            Node* node = st.top(); // 将栈顶的元素赋值给node
            st.pop(); // 出栈
            result.push_back(node->val); // 前序遍历
            for (int i = node->children.size() - 1; i >= 0; i--) {
                if (node->children[i] != NULL) {
                    st.push(node->children[i]); // 从右往左进行入栈操作
                }
            }
        }
        return result; // 返回结果数组

    }
};