代码随想录五刷day6

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

二叉树的层序遍历，就是图论中的广度优先搜索在二叉树中的应用，需要借助队列来实现（此时又发现队列的一个应用了）。

一、力扣144. 二叉树的前序遍历(递归)

/*** 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 {List<Integer> res = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {fun(root);return res;}public void fun(TreeNode root){if(root == null){return ;}res.add(root.val);fun(root.left);fun(root.right);}
}

二、力扣144. 二叉树的前序遍历(迭代)

/*** 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<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> deq = new LinkedList<>();if(root == null){return res;}TreeNode p = root;while(p != null || !deq.isEmpty()){if(p != null){res.add(p.val);deq.offerLast(p);p = p.left;}else{p = deq.pollLast();p = p.right;}}return res;}
}

三、力扣145. 二叉树的后序遍历(递归)

/*** 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 {List<Integer> res = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {fun(root);return res;}public void fun(TreeNode root){if(root == null){return ;}fun(root.left);fun(root.right);res.add(root.val);}
}

四、力扣145. 二叉树的后序遍历(迭代)

/*** 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<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> deq = new LinkedList<>();if(root == null){return res;}TreeNode p = root;while(p != null || !deq.isEmpty()){if(p != null){res.add(p.val);deq.offerLast(p);p = p.right;}else{p = deq.pollLast();p = p.left;}}Collections.reverse(res);return res;}
}

五、力扣94. 二叉树的中序遍历（递归）

/*** 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 {List<Integer> res = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {fun(root);return res;}public void fun(TreeNode root){if(root == null){return ;}fun(root.left);res.add(root.val);fun(root.right);}
}

六、力扣94. 二叉树的中序遍历迭代

/*** 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<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();Deque<TreeNode> deq = new LinkedList<>();if(root == null){return res;}TreeNode p = root;while(p != null || !deq.isEmpty()){if(p != null){deq.offerLast(p);p = p.left;}else{p = deq.pollLast();res.add(p.val);p = p.right;}}return res;}
}

七、力扣102. 二叉树的层序遍历

/*** 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>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();Deque<TreeNode> deq = new LinkedList<>();if(root == null){return res;}deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();List<Integer> list = new ArrayList<>();for(int i = 0; i < size; i ++){TreeNode p = deq.pollFirst();list.add(p.val);if(p.left != null){deq.offerLast(p.left);}if(p.right != null){deq.offerLast(p.right);}}res.add(list);}return res;}
}

八、力扣107. 二叉树的层序遍历 II

/*** 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>> levelOrderBottom(TreeNode root) {List<List<Integer>> res = new ArrayList<>();Deque<TreeNode> deq = new LinkedList<>();if(root == null){return res;}deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();List<Integer> list = new ArrayList<>();for(int i = 0; i < size; i ++){TreeNode p = deq.pollFirst();list.add(p.val);if(p.left != null){deq.offerLast(p.left);}if(p.right != null){deq.offerLast(p.right);}}res.add(list);}Collections.reverse(res);return res;}
}

九、力扣199. 二叉树的右视图

/*** 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<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();if(root == null){return res;}Deque<TreeNode> deq = new LinkedList<>();deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();for(int i = 0; i < size; i ++){TreeNode p = deq.pollFirst();if(i == size - 1){res.add(p.val);}if(p.left != null){deq.offerLast(p.left);}if(p.right != null){deq.offerLast(p.right);}}}return res;}
}

十、力扣637. 二叉树的层平均值

/*** 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<Double> averageOfLevels(TreeNode root) {List<Double> res = new ArrayList<>();if(root == null){return res;}Deque<TreeNode> deq = new LinkedList<>();deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();double sum = 0;for(int i = 0; i < size; i ++){TreeNode p = deq.pollFirst();sum += p.val;if(p.left != null){deq.offerLast(p.left);}if(p.right != null){deq.offerLast(p.right);}}res.add(sum/size);}return res;}
}

十一、力扣429. N 叉树的层序遍历

/*
// 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>> res = new ArrayList<>();if(root == null){return res;}Deque<Node> deq = new LinkedList<>();deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();List<Integer> list = new ArrayList<>();for(int i = 0; i < size; i ++){Node p = deq.pollFirst();list.add(p.val);for(Node n : p.children){deq.offerLast(n);}}res.add(list);}return res;}
}

十二、力扣515. 在每个树行中找最大值

/*** 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<Integer> largestValues(TreeNode root) {List<Integer> res = new ArrayList<>();if(root == null){return res;}Deque<TreeNode> deq = new LinkedList<>();deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();int val = Integer.MIN_VALUE;for(int i = 0; i < size; i ++){TreeNode p = deq.pollFirst();val = Math.max(p.val,val);if(p.left != null){deq.offerLast(p.left);}if(p.right != null){deq.offerLast(p.right);}}res.add(val);}return res;}
}

十三、力扣116. 填充每个节点的下一个右侧节点指针

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {public Node connect(Node root) {if(root == null){return root;}    Deque<Node> deq = new LinkedList<>();deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();Node pre = null;for(int i = 0; i < size; i ++){Node p = deq.pollFirst();if(i == 0){pre = p;}else{pre.next = p;pre = p;}if(p.left != null){deq.offerLast(p.lef`在这里插入代码片`t);}if(p.right != null){deq.offerLast(p.right);}}}return root;}
}

十四、力扣117. 填充每个节点的下一个右侧节点指针 II

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {public Node connect(Node root) {if(root == null){return root;}Deque<Node> deq = new LinkedList<>();deq.offerLast(root);while(!deq.isEmpty()){int size = deq.size();Node pre = null;for(int i = 0; i < size; i ++){Node p = deq.pollFirst();if(i == 0){pre = p;}else{pre.next = p;pre = p;}if(p.left != null){deq.offerLast(p.left);}if(p.right != null){deq.offerLast(p.right);}}}return root;}
}

十五、力扣104. 二叉树的最大深度(深度自顶向下)

/*** 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 {int max = Integer.MIN_VALUE;public int maxDepth(TreeNode root) {if(root == null){return 0;}fun(root,1);return max;}public void fun(TreeNode root, int leep){if(root == null){return;}max = Math.max(max, leep);fun(root.left,leep + 1);fun(root.right, leep + 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 maxDepth(TreeNode root) {return fun(root);}public int fun(TreeNode root){if(root == null){return 0;}int l = fun(root.left);int r = fun(root.right);return l > r ? l + 1 : r + 1;}
}

十六、力扣111. 二叉树的最小深度

/*** 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 minDepth(TreeNode root) {int min = 0;int res = Integer.MAX_VALUE;if(root == null){return 0;}Deque<TreeNode> deq = new LinkedList<>();deq.offerLast(root);while(!deq.isEmpty()){min ++;int size = deq.size();for(int i = 0; i < size; i ++){TreeNode p = deq.pollFirst();if(p.left == null && p.right == null){res = Math.min(res,min);}if(p.left != null){deq.offerLast(p.left);}if(p.right != null){deq.offerLast(p.right);}}}return res;}
}