博客

package com;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author liushihao <liushihao@kuaishou.com>
 * Created on 2021/4/12 4:38 下午
 */
public class TreeTest {

    public static void main(String[] args) {
        /*       1
              2   3   4
            5 6   7   8 9
         */
        NaryTreeNode root = new NaryTreeNode(1);
        root.addChildNode(new NaryTreeNode(2));
        root.addChildNode(new NaryTreeNode(3));
        root.addChildNode(new NaryTreeNode(4));
        List<NaryTreeNode> childList = root.getChildren();
        childList.get(0).addChildNode(new NaryTreeNode(5));
        childList.get(0).addChildNode(new NaryTreeNode(6));
        childList.get(1).addChildNode(new NaryTreeNode(7));
        childList.get(2).addChildNode(new NaryTreeNode(8));
        childList.get(2).addChildNode(new NaryTreeNode(9));
        for (int i : preOrder(root)) {
            System.out.print(i + "  ");
        }
        System.out.println();
        for (int i : postOrder(root)) {
            System.out.print(i + "  ");
        }
        System.out.println();
        for (List<Integer> i : levelOrder(root)) {
            for (int a : i) {
                System.out.print(a + "  ");
            }
            System.out.println();
        }
    }


    /**
     * 先序遍历：根左右
     * 利用栈模拟递归调用
     * 将根结点压入栈中，当栈不空时执行：
     * 弹出栈中结点，将其放入结果队列中
     * 将该结点的孩子按照倒序依次放入栈中
     */
    public static List<Integer> preOrder(NaryTreeNode root) {
        Deque<NaryTreeNode> stack = new LinkedList<>();
        List<Integer> pre = new LinkedList<>();
        if (root == null) return pre;
        stack.add(root);
        while (!stack.isEmpty()) {
            NaryTreeNode node = stack.pop();
            pre.add(node.getVal());
            Deque<NaryTreeNode> reChildren = new LinkedList<>(node.getChildren());
            while (!reChildren.isEmpty()) {
                stack.push(reChildren.pop());
            }
        }
        return pre;
    }

    /**
     * 后序遍历：左右根
     * 利用栈模拟递归调用
     * 将根结点压入栈中，当栈不空时执行：
     * 弹出栈中结点，将其头插放入结果队列中
     * 将该结点的孩子依次放入栈中
     * 
     * 
     * 其实后序遍历就是先序遍历的逆序列
     * 先序遍历：先遍历children再遍历root
     * 后序遍历：先遍历root再遍历children
     */
    public static List<Integer> postOrder(NaryTreeNode root) {
        Deque<NaryTreeNode> stack = new LinkedList<>();
        LinkedList<Integer> post = new LinkedList<>();
        if (root == null) return post;
        stack.add(root);
        while (!stack.isEmpty()) {
            NaryTreeNode node = stack.pop();
            // LinkedList的add方法是尾插法
            post.addFirst(node.getVal());
            for (NaryTreeNode child : node.getChildren()) {
                stack.push(child);
            }
        }
        return post;
    }

    /**
     * 层次遍历：
     * 利用队列模拟递归调用
     * 将根结点压入队中，当队不空时执行：
     * 获取当前队列长度，当迭代次数小于当前队列长度时：
     * 弹出当前队头结点，将其放入当前层的结果队列中
     * 将该结点的孩子依次放入队列中
     * 将当前层的结果队列放入结果队列中
     */


    public static List<List<Integer>> levelOrder(NaryTreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Queue<NaryTreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                NaryTreeNode node = queue.poll();
                level.add(node.getVal());
                queue.addAll(node.getChildren());
            }
            result.add(level);
        }
        return result;
    }
}


class NaryTreeNode {
    private int val;
    private List<NaryTreeNode> children;

    public NaryTreeNode(int val) {
        this.val = val;
        children = new ArrayList<NaryTreeNode>();
    }

    public NaryTreeNode(int val, List<NaryTreeNode> children) {
        this.val = val;
        if (children != null) this.children = children;
        else this.children = new ArrayList<NaryTreeNode>();
    }

    public int getVal() {
        return val;
    }

    public List<NaryTreeNode> getChildren() {
        return children;
    }

    public boolean isLeaf() {
        return children.isEmpty();
    }

    public boolean addChildNode(NaryTreeNode node) {
        children.add(node);
        return true;
    }
}