代码随想录四刷day16

本文主要是介绍代码随想录四刷day16，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

文章目录

前言
一、力扣111. 二叉树的最小深度
二、力扣222. 完全二叉树的节点个数
三、力扣110. 平衡二叉树
四、力扣257. 二叉树的所有路径

前言

本周的主题其实是简单但并不简单，本周所选的题目大多是看一下就会的题目，但是大家看完本周的文章估计也发现了，二叉树的简单题目其实里面都藏了很多细节。这些细节我都给大家展现了出来。

一、力扣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 {Deque<TreeNode> deq = new LinkedList<>();public int minDepth(TreeNode root) {if(root == null){return 0;}deq.offerLast(root);int res = 0;while(!deq.isEmpty()){int size = deq.size();res ++;for(int i = 0; i <size; i ++){TreeNode cur = deq.pollFirst();if(cur.left == null && cur.right == null){return res;}if(cur.left != null){deq.offerLast(cur.left);}if(cur.right != null){deq.offerLast(cur.right);}}}return res;}
}

递归后序

/*** 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) {if(root == null){return 0;}return fun(root,0);}public int fun(TreeNode root, int depth){if(root == null){return Integer.MAX_VALUE;}if(root.left == null && root.right == null){return depth+1;}int l = fun(root.left, depth+1);int r = fun(root.right, depth+1);return Math.min(l,r);}
}

前序递归

/*** 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 res = Integer.MAX_VALUE, len = 0;public int minDepth(TreeNode root) {if(root == null){return 0;}preOrder(root);return res;}public void preOrder(TreeNode root){if(root == null){return;}len ++;if(root.left == null && root.right == null){res = Math.min(res,len);}preOrder(root.left);preOrder(root.right);len --;}
}

二、力扣222. 完全二叉树的节点个数

后序

/*** 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 countNodes(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 + 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 {int res = 0;public int countNodes(TreeNode root) {fun(root);return res;}public void fun(TreeNode root){if(root == null){return;}res ++;fun(root.left);fun(root.right);}
}

三、力扣110. 平衡二叉树

/*** 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 {boolean flag = true;public boolean isBalanced(TreeNode root) {fun(root);return flag;}public int fun(TreeNode root){if(root == null){return 0;}int l = fun(root.left);int r = fun(root.right);if(Math.abs(l-r) > 1){flag = false;}return l > r ? l + 1 : r + 1;}
}

四、力扣257. 二叉树的所有路径

/*** 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<String> res = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {if(root == null){return res;}fun(root);return res;}public void fun(TreeNode root){if(root == null){return;}list.add(root.val);if(root.left == null && root.right == null){String s = "";for(int i = 0; i < list.size(); i ++){s += list.get(i);if(i < list.size()-1){s += "->";}}res.add(s);}fun(root.left);fun(root.right);list.remove(list.size()-1);}
}