讨论/《N 叉树》 - N 叉树的前序遍历/
《N 叉树》 - N 叉树的前序遍历
共 3 个回复

迭代

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            res.add(cur.val);
            for(int i=cur.children.size()-1;i>=0;i--){ //从最右侧子节点到最左侧子节点依次入栈
                stack.push(cur.children.get(i));
            }
        }
        return res;
    } 
}
1

迭代实现起来也还好,也就是树的深度优先遍历,但是需要注意节点进栈的顺序,靠右的节点应该优先进栈,二叉树的前序遍历也是这样的思路。
另外,这里用C++实现比用C实现更友好,C++的节点中是用vector来存储孩子节点的,里面没有存放空节点,也就不需要处理空节点。而且这样实现的N叉树要多少叉就能加多少叉。

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> pre;
        if(root==NULL)  return pre;
        Node *pos = root;
        stack<Node *> ST;
        ST.push(pos);
        int len;
        while(!ST.empty()){
            pos = ST.top(); ST.pop();
            pre.push_back(pos->val);
            len = (pos->children).size();
            for(int i=len-1; i>=0; --i){
                ST.push(pos->children[i]);
            }
        }
        return pre;
    }
};

基本出问题的点都在字节点顺序问题这个地方;