[数据结构与算法]二叉树层序历遍合集

637.二叉树的层平均值

力扣题目链接

class Solution {
     private List<Double> list = new ArrayList<>();
    
    public List<Double> averageOfLevels(TreeNode root) {
        DFS(root);
        return list;
    }

    void DFS(TreeNode node) {
        //定义队列
        Queue<TreeNode> queue = new LinkedList<>();
        if (node == null) return;
        queue.offer(node);
        while (!queue.isEmpty()) {
            long sum=0;
            int len = queue.size();
             int le=len;

            while (len > 0) {
                TreeNode poll = queue.poll();
                sum+=poll.val;
                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
                len--;
            }
            list.add(((double)sum/le));
        }
    }
}

429.N叉树的层序遍历

力扣题目链接

/*
// 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<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> levelOrder(Node root) {
        DFS(root);
        return list;
    }

    void DFS(Node node) {
        //定义队列
        Queue<Node> queue = new LinkedList<>();
        if (node == null) return;
        queue.offer(node);
        while (!queue.isEmpty()) {
            int len = queue.size();//获取本层的节点个数
            List<Integer> temp=new ArrayList<>();

            while (len > 0) {//进行本次节点对应值的统计，并将下一层节点加入队列中
                Node poll = queue.poll();
                temp.add(poll.val);

                if (poll.children != null && poll.children.size() != 0) {//若有子节点
                    for (Node child : poll.children) {
                        if (child != null) {
                            queue.offer(child);
                        }
                    }
                }
                len--;
            }
            list.add(temp);
        }
    }
}

515.在每个树行中找最大值

力扣题目链接

class Solution {
    private List<Integer> list = new ArrayList<>();

    public List<Integer> largestValues(TreeNode root) {
        DFS(root);
        return list;
    }

    void DFS(TreeNode node) {
        //定义队列
        Queue<TreeNode> queue = new LinkedList<>();
        if (node == null) return;
        queue.offer(node);
        while (!queue.isEmpty()) {
            int len = queue.size();//获取本层的节点个数
            int max=-2147483648;

            while (len > 0) {//进行本次节点对应值的统计，并将下一层节点加入队列中
                TreeNode poll = queue.poll();
                max = max > poll.val ? max : poll.val;

                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
                len--;
            }
            list.add(max);
        }
    }
}

116.填充每个节点的下一个右侧节点指针

力扣题目链接(opens new window)

class Solution {
         public Node connect(Node root) {
        DFS(root);
        return root;
    }

    void DFS(Node node) {
        //定义队列
        Queue<Node> queue = new LinkedList<>();
        if (node == null) return;
        queue.offer(node);
        while (!queue.isEmpty()) {
            int len = queue.size();//获取本层的节点个数

            while (len > 0) {//进行本层节点的历遍，并添加指针
                Node poll = queue.poll();
                if(len!=1){
                    poll.next = queue.peek();  
                }

                if (poll.left != null) {
                    queue.offer(poll.left);
                    queue.offer(poll.right);
                }
                
                len--;
            }
        }
    }
}