算法day26

第一题

429. N 叉树的层序遍历

本题的要求我们可以通过队列来辅助完成层序遍历；

如下图的n叉树：

步骤一：

我们定义一个队列，先进行根节点入队列操作；

步骤二：



我们进行当前队列每一个元素的出队列操作，并将这个节点的值存放在tmp列表中；

步骤三：



我们将上面根节点的子节点进行遍历，并一一放入到队列中，同时在进行出队列的时候，每出一个队列，该节点的值存放到tmp中，同时该节点的子节点也进行入队列操作；最后每一层的数值都会存放到惹他中，开始新的一层数据存储；

最后结束后如下图所示：



综上所述，代码如下：
/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> ret = new ArrayList<>();if(root == null) return ret;Queue<Node> q = new LinkedList<>();q.add(root);while(!q.isEmpty()){int sz = q.size();//当前队列里的节点个数List<Integer> tmp = new ArrayList<>();//用来统计本层的节点信息for(int i = 0; i<sz;i++){Node t = q.poll();tmp.add(t.val);for(Node child:t.children){if(child != null) q.add(chile);}}ret.add(tmp);   }return ret;}
}

第二题

103. 二叉树的锯齿形层序遍历

本题详细讲解如上题故事；

至于区别就是从上往下数二叉树的偶数层，在放入到tmp表中之后进行逆转操作，然后将这些元素在放入到ret总表中，返回；

综上所述，代码如下：

/*** Definition for a binary tree node.* public 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;*     }* }*/
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();if(root == null) return ret;Queue<TreeNode> q = new LinkedList<>();q.add(root);int floor = 1;while(!q.isEmpty()){int sz = q.size();//当前队列里的节点个数，当前层李米娜有多少元素List<Integer> tmp = new ArrayList<>();//用来统计本层的节点信息for(int i = 0; i<sz;i++){TreeNode t = q.poll();tmp.add(t.val);if(t.left != null)q.add(t.left);if(t.right != null)q.add(t.right);}if(floor % 2 == 0) Collections.reverse(tmp);ret.add(tmp);floor ++;}return ret;}
}

第三题

662. 二叉树最大宽度

下图两个实例如下所示：

解法：利用数组存储二叉树的方式，给结点编号；（堆的思想）

堆的数据结构：Pair<TreeNode树的结点,Integer定义的下标>

我们将每一层的这种堆结构的结点放入到队列中，则该层的宽度就是该层最右边的节点下标减去-该层最左边的节点下标+1；

同时每一层的宽度计算完成后，就将下一层的结点覆盖到队列中，重复计算每一层的节点宽度，直到求出最大值；

综上所述，代码如下：
/*** Definition for a binary tree node.* public 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;*     }* }*/
class Solution {public int widthOfBinaryTree(TreeNode root) {List<Pair<TreeNode,Integer>> q = new ArrayList<>();//用数组模拟队列q.add(new Pair<TreeNode,Integer>(root,1));int ret = 0;//记录最终结果while(!q.isEmpty()){//先更新一下这一层的宽度Pair<TreeNode,Integer> t1 = q.get(0);Pair<TreeNode,Integer> t2 = q.get(q.size()-1);ret = Math.max(ret,t2.getValue() - t1.getValue() +1);//让下一层进队List<Pair<TreeNode,Integer>> tmp = new ArrayList<>();//用数组模拟队列for(Pair<TreeNode,Integer> t:q){TreeNode node = t.getKey();int index = t.getValue();if(node.left != null){tmp.add(new Pair<TreeNode,Integer>(node.left,index*2));}if(node.right != null){tmp.add(new Pair<TreeNode,Integer>(node.right,index*2+1));}}q = tmp;}return ret;}
}