如果在工商局网站上做股权质押,如何在网站上做社交的链接,做网站用的图标,wordpress移动新闻一、基本层次遍历问题
1.二叉树的层次遍历 思路#xff1a;使用队列可以很好的保存遍历状态#xff0c;出队将结点左右子结点入队#xff0c;用size记录下一层的元素个数#xff0c;这样就能区分出层了
class Solution {public ListListInteger levelOr…一、基本层次遍历问题
1.二叉树的层次遍历 思路使用队列可以很好的保存遍历状态出队将结点左右子结点入队用size记录下一层的元素个数这样就能区分出层了
class Solution {public ListListInteger levelOrder(TreeNode root) {if(root null){return new LinkedList();}ListListInteger res new LinkedList();LinkedListTreeNode queue new LinkedList();queue.addFirst(root);while(!queue.isEmpty()){int size queue.size();LinkedListInteger list new LinkedList();while(size0){TreeNode node queue.remove();list.addLast(node.val);if(node.left ! null){queue.addLast(node.left);}if(node.right ! null){queue.addLast(node.right);}size--;}res.add(list);}return res;}
}
2.二叉树的层次遍历II 思路此题和上一题大同小异只需要在添加结果集的时候头插法就可以了。
class Solution {public ListListInteger levelOrderBottom(TreeNode root) {if(root null){return new LinkedList();}ListListInteger res new LinkedList();LinkedListTreeNode queue new LinkedList();queue.add(root);while(!queue.isEmpty()){int size queue.size();ListInteger list new LinkedList();while(size0){TreeNode node queue.removeFirst();size--;list.add(node.val);if(node.left! null){queue.add(node.left);}if(node.right! null){queue.add(node.right);}}res.add(0,list);}return res;}
}
3.锯齿形遍历 思路和层次遍历不同的是每层顺序奇偶方向交替用一个变量记录当前层的变量规则从左往右就是尾插法从右往左就是头插法
class Solution {public ListListInteger zigzagLevelOrder(TreeNode root) {if(root null){return new LinkedList();}ListListInteger res new LinkedList();LinkedListTreeNode queue new LinkedList();queue.add(root);int loop 1;while(!queue.isEmpty()){int size queue.size();LinkedListInteger list new LinkedList();for(int i 0;isize;i){TreeNode node queue.removeFirst();if(node.left! null){queue.add(node.left);} if(node.right! null){queue.add(node.right);}if(loop%20){list.addFirst(node.val);}else{list.add(node.val);}}res.add(list);loop;}return res;}
}
4.N叉树的层次遍历 思路此题和基本层次遍历不同的是每次不是添加左右孩子入队而是添加孩子列表入队把添加左右孩子替换成遍历添加列表就成。
class Solution {public ListListInteger levelOrder(Node root) {if(root null){return new LinkedList();}ListListInteger res new LinkedList();LinkedListNode queue new LinkedList();queue.addFirst(root);while(!queue.isEmpty()){int size queue.size();LinkedListInteger list new LinkedList();while(size0){Node node queue.remove();list.addLast(node.val);for(Node child : node.children){queue.add(child);}size--;}res.add(list);}return res;}
}
二、处理每层元素的问题
1.在每个树行中找最大值 思路还是和遍历大同小异现在不是将所有子结点都加入结果只取每层最大的比较一下就行
class Solution {public ListInteger largestValues(TreeNode root) {if(root null){return new LinkedList();}ListInteger res new LinkedList();LinkedListTreeNode queue new LinkedList();queue.addFirst(root);while(!queue.isEmpty()){int size queue.size();int max Integer.MIN_VALUE;while(size0){TreeNode node queue.remove();if(node.valmax){max node.val;}if(node.left ! null){queue.addLast(node.left);}if(node.right ! null){queue.addLast(node.right);}size--;}res.add(max);}return res;}
} 2.每个树行的平均值 思路和上一题找最大值没什么差别每层相加除以size就可以。
class Solution {public ListDouble averageOfLevels(TreeNode root) {if(root null){return new LinkedList();}ListDouble res new LinkedList();LinkedListTreeNode queue new LinkedList();queue.addFirst(root);while(!queue.isEmpty()){int size queue.size();Double mean 0.0;for(int i 0;isize;i){TreeNode node queue.remove();mean node.val;if(node.left ! null){queue.addLast(node.left);}if(node.right ! null){queue.addLast(node.right);}}res.add(mean/size);}return res;}
}
3.二叉树的右视图 思路层次遍历最后一个元素加入结果集就行。
class Solution {public ListInteger rightSideView(TreeNode root) {if(root null){return new LinkedList();}ListInteger res new LinkedList();LinkedListTreeNode queue new LinkedList();queue.addFirst(root);while(!queue.isEmpty()){int size queue.size();TreeNode node root;while(size0){node queue.remove();if(node.left ! null){queue.addLast(node.left);}if(node.right ! null){queue.addLast(node.right);}size--;}res.add(node.val);}return res;}
}
4.找树最小角的值 思路1层次遍历记录下每层第一个元素
2从右往左层次遍历最后一个元素
//方法一
class Solution {public int findBottomLeftValue(TreeNode root) {if(root null){return -1;}int res -1;LinkedListTreeNode queue new LinkedList();queue.add(root);while(queue.size()0){int size queue.size();res queue.get(0).val;while(size0){TreeNode node queue.remove();size--;if(node.left ! null){queue.add(node.left);}if(node.right ! null){queue.add(node.right);}}}return res;}
}//方法二
class Solution {public int findBottomLeftValue(TreeNode root) {if(root null){return -1;}int res -1;QueueTreeNode queue new LinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNode node queue.poll();res node.val;if(node.right ! null){queue.offer(node.right);} if(node.left ! null){queue.offer(node.left);}}return res;}
}
