590_N叉树的后序遍历

简介: 590_N叉树的后序遍历

590_N叉树的后序遍历

 

package 二叉树.BT;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
/**
 * https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
 * @author Huangyujun
 *
 */
public class _590_N叉树的后序遍历 {
    public 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;
        }
    }
    //递归
    List<Integer> list = new ArrayList<Integer>();
     public List<Integer> postorder1(Node root) {
         if(root == null)    return list;
         for(Node node: root.children) {
             postorder(node);
         }
         //拿到当前结点
         list.add(root.val);
         return list;
     }    
     //使用迭代
     public List<Integer> postorder(Node root) {
          LinkedList<Integer> res = new LinkedList<>();
            if (root == null) {
                return res;
            }
            Deque<Node> stack = new LinkedList<>();
            stack.addLast(root);
            while (!stack.isEmpty()) {
                Node node = stack.poll();
                //实现数据的倒序(改变先后顺序):不断的插入当前结点第一个位置
                res.addFirst(node.val);    //为啥要倒序:因为当前第一个元素插入的是根
                                        //而后序是 孩子们 根
                                        //且倒序:实现了 1 2 3 4 (addFirst)
                for (Node item : node.children) {
                    stack.push(item); // 1 2 3 4 (头)
                }
            }
            return res;
     }     
}
目录
相关文章
|
6月前
|
Python
二叉树前中后序遍历
这段内容是关于二叉树的前序、中序和后序遍历的Python实现。`Solution`类包含三个方法:`preorderTraversal`、`inorderTraversal`和`postorderTraversal`,分别返回二叉树节点值的前序、中序和后序遍历列表。每个方法都是递归的,遍历顺序为:前序(根-左-右)、中序(左-根-右)、后序(左-右-根)。
58 4
|
6月前
|
算法
【二叉树】层序遍历
【二叉树】层序遍历
67 0
05_二叉树的层次遍历II
05_二叉树的层次遍历II
08_N叉树的层序遍历
08_N叉树的层序遍历
04_二叉树的层序遍历
04_二叉树的层序遍历
|
6月前
|
存储
什么?二叉树的反前序遍历?
什么?二叉树的反前序遍历?
|
6月前
|
存储 算法 前端开发
589. N 叉树的前序遍历
589. N 叉树的前序遍历
33 0
|
6月前
|
C++
二叉树的前序遍历(C++)
二叉树的前序遍历(C++)
49 0
二叉树的前序遍历(C++)
|
存储 搜索推荐
【二叉树OJ题(二)】前序遍历&&中序遍历&&后序遍历&&另一颗树的子树&&二叉树遍历&&平衡二叉树(下)
【二叉树OJ题(二)】前序遍历&&中序遍历&&后序遍历&&另一颗树的子树&&二叉树遍历&&平衡二叉树(下)