编程导航第六关——白银挑战

树的层次遍历

• LeetCode102 题目要求：给你一个二叉树，请你返回其按层序遍历得到的节点值。(即逐层地，从左到右访问所有节点)。
• 思路：
  • 我们根据队列的特点，先进先出；要实现全部节点的层次遍历，再次我们采用队列的数据结构，当队列中元素为空时，则代表树已被遍历完成，所以我们在循环时的条件就是quene.size>0
  • 我们首先弹出元素，然后将该节点的子节点压入队列当中，这是，队列中的出队顺序就是层次遍历的顺序
  • 在本题中，我们需要实现每一层元素值的分别记录，所以需要得到每一层对应的节点数是多少；
  • 每一次的节点数就是队列的元素个数；只要出队，便是size-1，同时在出队时会将子节点压入队列中，当size==0时，那么这一层的元素已全部遍历完，同时此时队列中元素的个数，便是下一层的size

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);//        遍历条件while (queue.size() > 0) {int size = queue.size();final ArrayList<Integer> temp = new ArrayList<>();for (int i = 0; i < size; i++) {TreeNode peek = queue.poll();temp.add(peek.val);if (peek.left != null) {queue.add(peek.left);}if (peek.right != null) {queue.add(peek.right);}}result.add(temp);}return result;}

层次遍历——自底向上

• LeetCode 107.给定一个二叉树，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。
• 思路：
  • 本题的解题思路与上题基本类似，区别在于最后的结果列表需要倒序返回，可采用链表的结构，每次向结果集中添加元素时，添加在链表的首位

 public List<List<Integer>> levelOrderBottom(TreeNode root) {LinkedList<List<Integer>> result = new LinkedList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.add(root);while (queue.size() > 0) {int size = queue.size();ArrayList<Integer> temp = new ArrayList<>();for (int i = 0; i < size; i++) {TreeNode poll = queue.poll();temp.add(poll.val);if (poll.left != null) {queue.add(poll.left);}if (poll.right != null) {queue.add(poll.right);}}result.addFirst(temp);}return result;}

层次遍历——锯齿形遍历

• LeetCode103 题，要求是：给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
• 思路：
  • 在实现层次遍历的基础上，对结果集中的列表选择元素的节点是在列表的末尾，还是列表的开头
  • 如果是奇数层，在首位
  • 如果是偶数层，在末尾

 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {ArrayList<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}LinkedList<TreeNode> queue = new LinkedList<>();int cen = 1;queue.add(root);while (queue.size() > 0) {int size = queue.size();LinkedList<Integer> temp = new LinkedList<>();for (int i = 0; i < size; i++) {TreeNode poll = queue.poll();if (cen % 2 == 0) {temp.addFirst(poll.val);}else {temp.add(poll.val);}if (poll.left != null) {queue.add(poll.left);}if (poll.right != null) {queue.add(poll.right);}}result.add(temp);cen++;}return result;}

N叉树的遍历

• LeetCode429 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

 public List<List<Integer>> levelOrder(Node root) {Queue<Node> nodes = new LinkedList<>();ArrayList<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}nodes.add(root);while (nodes.size() > 0) {int size = nodes.size();ArrayList<Integer> temp = new ArrayList<>();for (int i = 0; i < size; i++) {final Node poll = nodes.poll();temp.add(poll.val);List<Node> children = poll.children;if (children != null) {for (int j = 0; j < children.size(); j++) {Node node = children.get(j);if (node != null) {nodes.add(node);}}}}result.add(temp);}return result;}

几个处理每层元素的题目

在每个树行中找最大值

• LeetCode 515题目要求：给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
• 思路：
  • 使用层次遍历，定义每一层的第一个是最大值，遍历每一层的节点，找出最大值

public List<Integer> largestValues(TreeNode root) {final ArrayList<Integer> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return result;}queue.add(root);while (queue.size() > 0) {int size = queue.size();int max=queue.peek().val;for (int i = 0; i < size; i++) {final TreeNode poll = queue.poll();if (poll.val>max){max=poll.val;}if (poll.left!=null){queue.add(poll.left);}if (poll.right!=null){queue.add(poll.right);}}result.add(max);}return result;}

在每个树行中找平均值

• LeetCode 637 要求给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
• 思路：同上

public List<Double> averageOfLevels(TreeNode root) {final ArrayList<Double> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return result;}queue.add(root);while (queue.size() > 0) {int size = queue.size();ArrayList<Integer> temp = new ArrayList<>();for (int i = 0; i < size; i++) {final TreeNode poll = queue.poll();temp.add(poll.val);if (poll.left != null) {queue.add(poll.left);}if (poll.right != null) {queue.add(poll.right);}}
//            计算平均值double sum = 0;for (int i = 0; i < temp.size(); i++) {sum += temp.get(i);}double average = sum / temp.size();result.add(average);}return result;}

二叉树的右视图

• LeetCode 199题目要求是：给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
• 思路：
  • 本质上是取每层最后一个元素到结果集中，采取层次遍历的方法，具体思路同上

 public List<Integer> rightSideView(TreeNode root) {ArrayList<Integer> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return result;}queue.add(root);while (queue.size() > 0) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}if (i == size - 1) {result.add(node.val);}}}return result;}

最底层 最左边

• Offer II 045.给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
• 思路：
  • 层次遍历最后一个输出的元素是最右边，最底部；
  • 要获取最左边，最底部，翻转每次元素节点，实现每层从右往左遍历
  • 返回值的条件便是，当最后一个节点弹出时（队列为空时）返回该节点的值

public int findBottomLeftValue(TreeNode root) {
//        ArrayList<Integer> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return 0;}queue.add(root);while (queue.size() > 0) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.right != null) {queue.add(node.right);}if (node.left != null) {queue.add(node.left);}if (queue.size() == 0) {return node.val;}}}return 0;}