天天看點

算法:N叉樹的後序周遊算法分享

//1.遞歸
	public List<Integer> postorder(Node root) {
		List<Integer> list = new ArrayList<Integer>();
		if (root == null) return list;
		
		post_order(list,root.children);
		list.add(root.val);
		
		return list;
    }
	
	public void post_order(List<Integer> list,List<Node> subList) {
		if (subList == null || subList.size() == 0) return;
		
		for (Node n : subList) {
			if (n == null) return;
			post_order(list, n.children);
			list.add(n.val);
		}
	}
           
//2.疊代
	public List<Integer> postorder(Node root) {
		LinkedList<Node> input = new LinkedList<>();
		LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        input.add(root);
        while (!input.isEmpty()) {
            Node node = input.pollLast();
            output.addFirst(node.val);
            if (node.children != null) {
	            for (Node item : node.children) {
	            	if (item != null) {
	            		input.add(item);						
					}
	            }
            }
        }
        return output;		
    }