[二叉树] 特定深度节点链表

前言

接上篇，将二叉树的层序遍历进行应用

题目

特定深度节点链表

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

题目拆解

这是一道比较标准的层序二叉树的题目，做法也很基础，就是一层一层遍历二叉树，然后把对应的节点拼成一个链表即可。

按步骤划分
1、获取二叉树的深度
2、构建结果集，数组下标代表对应的层数
3、层序遍历每层，将新得到的节点头查到对应层的结果集中，头插是为了方便，不用遍历每层找到最后一个节点，但是遍历的时候也要注意，要从右到左遍历。
4、重新将结果插入结果集
5、返回结果。

代码

深度优先

class Solution {

    private ListNode[] res = null;

    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) return new ListNode[0];

        // 获取树的深度
        int deepth = getDeep(tree);
        // 构建每一层的结果集
        res = new ListNode[deepth];
        dfs(tree, 0);
        return res;
    }

    int getDeep(TreeNode treeNode) {
        if (treeNode == null) return 0;
        // 获取左子树与右子树的深度
        return Math.max(getDeep(treeNode.left), getDeep(treeNode.right)) + 1;
    }

    // 深度优先
    void dfs(TreeNode treeNode, int deep) {
        // 当前节点是null,直接return;
        if (treeNode == null) return;
        // 找到当前节点所在深度对应的链表;
        ListNode listNode = res[deep];
        ListNode head = new ListNode(treeNode.val);
        if (listNode == null) {
            // 如果链表不存在,说明当前节点是该层第一个节点
            res[deep] = new ListNode(treeNode.val);
        } else {
            // 将当前节点赋值到链表的头部
            head.next = listNode;
            res[deep] = head;
        }
        // 继续广度优先左子树和右子树
        // 因为是头插,所以先从右侧遍历,这样遍历的最终结果是左边第一个节点到右边第一个节点
        dfs(treeNode.right, deep + 1);
        dfs(treeNode.left, deep + 1);
    }

}

广度优先

class Solution {

    private ListNode[] res = null;

    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) return new ListNode[0];

        // 获取树的深度
        int deepth = getDeep(tree);
        // 构建每一层的结果集
        res = new ListNode[deepth];
        bfs(tree,0);
        return res;
    }

    int getDeep(TreeNode treeNode) {
        if (treeNode == null) return 0;
        // 获取左子树与右子树的深度
        return Math.max(getDeep(treeNode.left), getDeep(treeNode.right)) + 1;
    }
    // 广度优先
    void bfs(TreeNode treeNode,int deep) {
        // 用队列维护每层的节点
        Queue<TreeNode> queue = new LinkedList<>();
        // 将根节点插入到当前队列中
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            // 获取当前层的节点总数
            int size = queue.size();

            // 两个指针,制造一个哑结点
            ListNode head = new ListNode(-1);
            ListNode curr = head;
            while (size > 0) {
                // 取出一个节点
                TreeNode poll = queue.poll();
                ListNode prev = new ListNode(poll.val);
                curr.next = prev;
                curr = prev;
                if (poll.left != null) queue.add(poll.left);
                if (poll.right != null) queue.add(poll.right);
                size--;
            }
            res[deep] = head.next;
            deep++;
        }

    }
}

总结

试着中dfs和bfs分别写了一下代码，顺手上还是dfs更顺手，但是bfs也省却了一点null值判断，以后二叉树相关题目，可以考虑两种方法继续尝试。