LeetCode_Stack_589. N-ary Tree Preorder Traversal N 叉树的前序遍历【栈，迭代】【简单】

目录

​​一，题目描述​​

​​英文描述​​

​​中文描述​​

​​示例与说明​​

​​二，解题思路​​

​​三，AC代码​​

​​C++​​

​​Java​​

​​四，解题过程​​

​​第一博​​

一，题目描述

英文描述

Given the root of an n-ary tree, return the preorder traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See examples)

中文描述

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

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

进阶：

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

示例与说明

示例 1：

示例 2：

提示：

• N 叉树的高度小于或等于 1000
• 节点总数在范围 [0, 10^4] 内

来源：力扣（LeetCode）
链接：​​​力扣​​ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路

和这一题类似，都是采用栈的迭代方法

​​@&再见萤火虫&【LeetCode_Stack_144. Binary Tree Preorder Traversal 二叉树的前序遍历【栈，迭代】【简单】】

区别在于，本题需要借助一个索引栈indexStack来记录当前遍历到节点的哪一个孩子。

关键点如下：

• temp标记根节点，一路向左。走不动了再根据索引栈和节点栈判断下一个temp，然后重新进入循环；
• 每个节点第一次入栈时，当前索引0跟着入栈。此后节点栈和索引栈保持一致操作，即出栈、入栈操作保持一致；
• 每次用到栈顶元素时，记得判断栈非空；

三，AC代码

C++

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans, indexStack;
        vector<Node*> nodeStack;
        if (root == nullptr) return ans;
        nodeStack.push_back(root);
        indexStack.push_back(0);
        ans.push_back(root->val);
        if (root->children.size() == 0) return ans;
        root = root->children[0];
        while (!nodeStack.empty() && !indexStack.empty()) {
            while (root != nullptr) {
                nodeStack.push_back(root);
                indexStack.push_back(0);
                ans.push_back(root->val);
                if (root->children.size() != 0) {
                    root = root->children[0];
                } else {
                    root = nullptr;
                }
            }
            int index = indexStack.back() + 1;
            while (!nodeStack.empty() && 
            (nodeStack.back()->children.size() == 0 || index >= nodeStack.back()->children.size())) {
                nodeStack.pop_back();
                indexStack.pop_back();
                if (!indexStack.empty()) {
                    index = indexStack.back() + 1;
                }
            }
            if (!nodeStack.empty()) {
                indexStack.pop_back();
                indexStack.push_back(index);
                root = nodeStack.back()->children[index];
            } else root = nullptr;
        }
        return ans;
    }
};

Java

class Solution {
    public List<Integer> preorder(Node root) {
        Deque<Node> nodeStack = new LinkedList<>();
        Deque<Integer> indexStack = new LinkedList<>();
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        nodeStack.push(root);
        indexStack.push(0);
        ans.add(root.val);
        if (root.children.size() == 0) return ans;
        Node temp = root.children.get(0);
        int index = 0;
        while (!nodeStack.isEmpty() && !indexStack.isEmpty()) {
            while (temp != null) {
                nodeStack.push(temp);
                indexStack.push(0);
                ans.add(temp.val);          // 节点入栈时，将节点值加入到结果数组中
                if (temp != null && temp.children.size() != 0) {
                    temp = temp.children.get(0);
                } else {                    // 到达叶节点
                    temp = null;
                }
            }
            if (nodeStack.peek().children.size() == 0) {
                nodeStack.pop();
                indexStack.pop();
            }
            index = indexStack.peek() + 1;  // 表示下一个要访问的节点索引
            // 索引栈不为空且索引值不超过栈顶节点孩子数组的最大边界时
            while (!indexStack.isEmpty() && index >= nodeStack.peek().children.size()) {
                nodeStack.pop();
                indexStack.pop();
                if (!indexStack.isEmpty()) index = indexStack.peek() + 1;
            }
            if (!indexStack.isEmpty()) {
                indexStack.pop();
                indexStack.push(index);     // 此时index即为下一个要访问的节点索引
                temp = nodeStack.peek().children.get(index);
            }
        }
        return ans;
    }
}

四，解题过程

第一博

知道要引入索引栈辅助定位，但是细节部分还是调了很久。还有，为啥迭代算法效率这么低？？？