N叉树的前序遍历

题目链接


N叉树前序遍历的结果为： 
[1,3,5,6,2,4]

思路一：recursion

代码如下：

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

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

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if(root == null){
            return list;
        }
        list.add(root.val);
        while(!root.children.isEmpty()){
            preorder(root.children.remove(0));
        }
        return list;
    }
}

本代码并没有考虑到维护原二叉树的结构，而是选择使用了remove函数。如果面试的时候遇到此类问题，可以和面试官交流，如果需要保持二叉树的原有结构则可以选择正常的遍历~
时间复杂度：O(N)
额外空间复杂度：O(N)

O(N)为本题最坏情况的额外空间复杂度，也就是二叉树退化为链表时，递归栈的深度为N

执行结果:


思路二：stack

同二叉树的前序遍历相同，二叉树的前序遍历，需要按照先右节点后左节点的顺序入栈。本题则是将arrayList的每一个节点从后向前地push到栈中，本代码依旧没有考虑维护原有的二叉树 :-)

代码如下：

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

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

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if(root != null){
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                root = stack.pop();
                list.add(root.val);
                while(!root.children.isEmpty()){
                    stack.push(root.children.remove(root.children.size() - 1));
                }
            }
        }
        return list;
    }
}

执行结果如下:


N叉树的后序遍历

题目链接
N叉树的后序遍历：

对于上面这棵二叉树，后序遍历的结果为：

[5,6,3,2,4,1]

思路一：recursion

代码如下：

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

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

class Solution {
    private List<Integer> list = new ArrayList<>();
    public List<Integer> postorder(Node root) {
        if(root == null){
            return list;
        }
        List<Node> children = root.children;
        while(!children.isEmpty()){
            postorder(children.remove(0));
        }
        list.add(root.val);
        return list;
    }
}

该算法的时间复杂度:
因为N叉树的每个节点相当于只遍历了一遍，所以时间复杂度为O(N),额外空间上来讲，需要递归栈，最大的递归深度为，N叉树退化为一个链表的时候，额外空间复杂度O(N)
代码执行结果:


思路二：stack

对于一棵树的后序遍历而言，我们只需要使用两个栈，只不过入栈的顺序保证和先序遍历相反即可；关于二叉树的先序后序遍历，请见文章：二叉树基础题
代码如下：

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

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

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

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if(root != null){
            Stack<Node> stack1 = new Stack<>();
            Stack<Node> stack2 = new Stack<>();
            stack1.push(root);
            while(!stack1.isEmpty()){
                root = stack1.pop();
                stack2.push(root);
                while(!root.children.isEmpty()){
                    stack1.push(root.children.remove(0));
                }
            }
            while(!stack2.isEmpty()){
                list.add(stack2.pop().val);
            }
        }
        return list;
    }
}

该算法的时间复杂度为:O(N),额外使用了两个栈，额外空间复杂度为O(N);
代码执行结果惨不忍睹：