网站新类型,福州网站外包,做设计适合关注的网站,google建网站编程导航第六关——白银挑战
树的层次遍历
LeetCode102 题目要求#xff1a;给你一个二叉树#xff0c;请你返回其按层序遍历得到的节点值。(即逐层地#xff0c;从左到右访问所有节点)。思路#xff1a; 我们根据队列的特点#xff0c;先进先出#xff1b;要实现全部节…编程导航第六关——白银挑战
树的层次遍历
LeetCode102 题目要求给你一个二叉树请你返回其按层序遍历得到的节点值。(即逐层地从左到右访问所有节点)。思路 我们根据队列的特点先进先出要实现全部节点的层次遍历再次我们采用队列的数据结构当队列中元素为空时则代表树已被遍历完成所以我们在循环时的条件就是quene.size0我们首先弹出元素然后将该节点的子节点压入队列当中这是队列中的出队顺序就是层次遍历的顺序在本题中我们需要实现每一层元素值的分别记录所以需要得到每一层对应的节点数是多少每一次的节点数就是队列的元素个数只要出队便是size-1同时在出队时会将子节点压入队列中当size0时那么这一层的元素已全部遍历完同时此时队列中元素的个数便是下一层的size
public ListListInteger levelOrder(TreeNode root) {ListListInteger result new ArrayList();if (root null) {return result;}QueueTreeNode queue new LinkedList();queue.add(root);// 遍历条件while (queue.size() 0) {int size queue.size();final ArrayListInteger 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 ListListInteger levelOrderBottom(TreeNode root) {LinkedListListInteger result new LinkedList();if (root null) {return result;}QueueTreeNode queue new LinkedListTreeNode();queue.add(root);while (queue.size() 0) {int size queue.size();ArrayListInteger 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 ListListInteger zigzagLevelOrder(TreeNode root) {ArrayListListInteger result new ArrayList();if (root null) {return result;}LinkedListTreeNode queue new LinkedList();int cen 1;queue.add(root);while (queue.size() 0) {int size queue.size();LinkedListInteger 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 ListListInteger levelOrder(Node root) {QueueNode nodes new LinkedList();ArrayListListInteger result new ArrayList();if (root null) {return result;}nodes.add(root);while (nodes.size() 0) {int size nodes.size();ArrayListInteger temp new ArrayList();for (int i 0; i size; i) {final Node poll nodes.poll();temp.add(poll.val);ListNode 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 ListInteger largestValues(TreeNode root) {final ArrayListInteger result new ArrayList();QueueTreeNode queue new LinkedList();if (root null) {return result;}queue.add(root);while (queue.size() 0) {int size queue.size();int maxqueue.peek().val;for (int i 0; i size; i) {final TreeNode poll queue.poll();if (poll.valmax){maxpoll.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 ListDouble averageOfLevels(TreeNode root) {final ArrayListDouble result new ArrayList();QueueTreeNode queue new LinkedList();if (root null) {return result;}queue.add(root);while (queue.size() 0) {int size queue.size();ArrayListInteger 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 ListInteger rightSideView(TreeNode root) {ArrayListInteger result new ArrayList();QueueTreeNode 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) {
// ArrayListInteger result new ArrayList();QueueTreeNode 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;}
