二叉树的按层遍历

作者：Grey

原文地址：

博客园：二叉树的按层遍历

CSDN：二叉树的按层遍历

说明

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

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;
    }

类似问题

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

题目链接见：LeetCode 107. Binary Tree Level Order Traversal II

主要思路，由于要自底向上，所以，可以将按层收集的数据结构由队列改成栈就可以了，然后到最后再把栈内收集的结果弹出即可。

代码如下

  public List<List<Integer>> levelOrderBottom(TreeNode root) {
    if (null == root) {
      return new ArrayList<>();
    }
    Deque<List<Integer>> stack = new ArrayDeque<>();
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> levelRecords = new ArrayList<>();
    TreeNode curEnd = root;
    TreeNode nextEnd = null;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
      TreeNode poll = queue.poll();
      levelRecords.add(poll.val);
      if (null != poll.left) {
        queue.offer(poll.left);
        nextEnd = poll.left;
      }
      if (null != poll.right) {
        queue.offer(poll.right);
        nextEnd = poll.right;
      }
      if (poll == curEnd) {
        curEnd = nextEnd;
        stack.push(levelRecords);
        levelRecords = new ArrayList<>();
      }
    }
    while (!stack.isEmpty()) {
      result.add(stack.poll());
    }
    return result;
  }

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。

题目链接见：LeetCode 637. Average of Levels in Binary Tree

本题的思路也类似，就是用一个变量先记录每一层的数量，然后用另外一个变量记录每一层的结点值之和，到遍历到下一层的时候，结算上一层结点值的平均值即可。

代码如下

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
    if (null == root) {
      return new ArrayList<>();
    }
    List<Double> result = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode curEnd = root;
    TreeNode nextEnd = null;
    int numOfNodes = 0;
    Double sumOfNodesVal = 0d;
    queue.offer(root);
    while (!queue.isEmpty()) {
      TreeNode poll = queue.poll();
      if (null != poll.left) {
        queue.offer(poll.left);
        nextEnd = poll.left;
      }
      if (null != poll.right) {
        queue.offer(poll.right);
        nextEnd = poll.right;
      }
      numOfNodes++;
      sumOfNodesVal += poll.val;
      if (poll == curEnd) {
        result.add(sumOfNodesVal / numOfNodes);
        sumOfNodesVal = 0d;
        numOfNodes = 0;
        curEnd = nextEnd;
      }
    }

    return result;
  }
}

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

题目链接见：

LeetCode 116. Populating Next Right Pointers in Each Node

LeetCode 117. Populating Next Right Pointers in Each Node II

本题的主要思路也是基于二叉树的按层遍历，只不过在遍历完每一层后，把这一层的数据用链表串起来。

所以，需要获取每一层的数量，且设置一个 pre 变量，用于记录每次遍历完一层的最后一个位置，因为要用这个位置去连下一层的开始位置。

完整代码如下

class Solution {
    public static Node connect(Node root) {
        if (null == root) {
      return null;
    }
    Node pre = null;
    int size;
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
      size = queue.size();
      for (; size > 0; size--) {
        Node p = queue.poll();
        if (pre != null) {
          pre.next = p;
        }
        pre = p;
        if (null != p.left) {
          queue.offer(p.left);
        }
        if (null != p.right) {
          queue.offer(p.right);
        }
      }
      pre = null;
    }
    return root;
  }
}

更多

算法和数据结构笔记

参考资料

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