二叉树的按层遍历

作者：Grey

原文地址：二叉树的按层遍历

说明

本文主要介绍了二叉树的按层遍历。并且分别用如下三种方式实现：

1. 哈希表结合LinkedList
2. 使用系统自带的LinkedList
3. 自定义队列

以上方法只是空间复杂度有所差异，时间复杂度上都是一样的。

示例二叉树

这个二叉树按层次遍历的结果就是

1->2->3->4->5->6->7->8->9->10->11->12->13

数据结构

public static class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode() {    }    TreeNode(int val) {        this.val = val;    }    TreeNode(int val, TreeNode left, TreeNode right) {        this.val = val;        this.left = left;        this.right = right;    }}

测评链接

LeetCode 102. Binary Tree Level Order Traversal

流程

整个过程最核心的地方就是需要记录当前层什么时候遍历完毕以及当前弹出的节点在第几层。

方法1中，使用哈希表来存每个节点当前所在的层，头节点默认在第0层，且将头节点首先入队列，然后在弹出的过程中，将弹出节点的子节点放入哈希表，且把层数设置为当前节点的层数+1，同时把子节点放入队列，然后进行同样的队列弹出操作，直到队列空。

方法1的完整代码如下

   public static List<List<Integer>> levelOrder(TreeNode head) {        if (head == null) {            return new ArrayList<>();        }        List<List<Integer>> ans = new ArrayList<>();        // 记录某个节点在第几层        Map<TreeNode, Integer> map = new HashMap<>();        Queue<TreeNode> queue = new LinkedList<>();        // 当前是第几层        int curLevel = 0;        TreeNode cur = head;        queue.offer(cur);        map.put(cur, curLevel);        List<Integer> levelRecords = new ArrayList<>();        while (!queue.isEmpty()) {            TreeNode c = queue.poll();            int level = map.get(c);            if (c.left != null) {                queue.offer(c.left);                map.put(c.left, level + 1);            }            if (c.right != null) {                queue.offer(c.right);                map.put(c.right, level + 1);            }            if (curLevel == level) {                levelRecords.add(c.val);            } else {                ans.add(levelRecords);                levelRecords = new ArrayList<>();                levelRecords.add(c.val);                curLevel = level;            }        }        // 记得要存最后一层的数据        ans.add(levelRecords);        return ans;    }

方法2省略了一个哈希表，使用了两个变量来判断层数的变化，分别是：

// 遍历到的当前层的最后一个位置TreeNode curEnd; // 下一层的最后一个位置TreeNode nextEnd;

在队列每次弹出元素的时候，设置nextEnd变量，同时，如果弹出的元素等于curEnd，说明已经到当前层的结尾了，就可以收集这一层的答案了。

方法2的完整代码如下

public static List<List<Integer>> levelOrder2(TreeNode head) {        if (head == null) {            return new ArrayList<>();        }        List<List<Integer>> ans = new ArrayList<>();        List<Integer> levelRecords = new ArrayList<>();        Queue<TreeNode> queue = new LinkedList<>();        TreeNode curEnd = head;        TreeNode nextEnd = null;        queue.offer(curEnd);        while (!queue.isEmpty()) {            TreeNode c = queue.poll();            levelRecords.add(c.val);            if (c.left != null) {                queue.offer(c.left);                // 弹出的时候，设置nextEnd                nextEnd = c.left;            }            if (c.right != null) {                queue.offer(c.right);               // 弹出的时候，设置nextEnd                nextEnd = c.right;            }            if (c == curEnd) {                // 即将要来到新的一层了                curEnd = nextEnd;                ans.add(levelRecords);                levelRecords = new ArrayList<>();            }        }        return ans;    }

方法3只是把方法2中的链表和队列换成自己实现的链表和队列结构，大思路上和方法2一样，我们可以自己实现一个链表和队列，实现最简单的poll和offer方法即可，自定义的链表如下：

  // 自定义链表  public static class MyNode {        public TreeNode data;        public MyNode next;	        public MyNode(TreeNode node) {            data = node;        }    }	// 自定义队列    public static class MyQueue {        public MyNode front;        public MyNode end;        public int size;        public MyQueue() {            front = null;            end = null;        }        public void offer(MyNode c) {            size++;            if (front == null) {                front = c;            } else {                end.next = c;            }            end = c;        }        public boolean isEmpty() {            return size == 0;        }        public MyNode poll() {            size--;            MyNode ans = front;            front = front.next;            ans.next = null;            return ans;        }    }

然后把方法2中的Java自带的LinkedList换成我们自己实现的链表和队列，完整代码如下

    public static List<List<Integer>> levelOrder(TreeNode root) {        List<List<Integer>> ans = new ArrayList<>();        if (root == null) {            return ans;        }        MyNode head = new MyNode(root);        MyQueue queue = new MyQueue();        queue.offer(head);        MyNode curEnd = head;        MyNode nextEnd = null;        List<Integer> item = new ArrayList<>();        MyNode t;        while (!queue.isEmpty()) {            MyNode c = queue.poll();            if (c.data.left != null) {                t = new MyNode(c.data.left);                queue.offer(t);                nextEnd = t;            }            if (c.data.right != null) {                t = new MyNode(c.data.right);                queue.offer(t);                nextEnd = t;            }            item.add(c.data.val);            if (curEnd.data == c.data) {                ans.add(item);                item = new ArrayList<>();                curEnd = nextEnd;            }        }        return ans;    }

二叉树的先，中，后序遍历

见笔记：二叉树的先，中，后序遍历

更多

算法和数据结构笔记

参考资料

算法和数据结构体系班-左程云