如何在网站做404页面,专业建站公司提供详细的功能描述及报价,wordpress顶部代码,网站推广是怎么推广的力扣爆刷第141天之二叉树十连刷#xff08;翻转、对称、深度、平衡、路径#xff09; 文章目录 力扣爆刷第141天之二叉树十连刷#xff08;翻转、对称、深度、平衡、路径#xff09;一、226. 翻转二叉树二、101. 对称二叉树三、104. 二叉树的最大深度四、111. 二叉树的最小…力扣爆刷第141天之二叉树十连刷翻转、对称、深度、平衡、路径 文章目录 力扣爆刷第141天之二叉树十连刷翻转、对称、深度、平衡、路径一、226. 翻转二叉树二、101. 对称二叉树三、104. 二叉树的最大深度四、111. 二叉树的最小深度五、222. 完全二叉树的节点个数六、110. 平衡二叉树七、257. 二叉树的所有路径八、404. 左叶子之和九、513. 找树左下角的值十、112. 路径总和 一、226. 翻转二叉树
题目链接https://leetcode.cn/problems/invert-binary-tree/description/ 思路直接前序遍历然后在遍历的过程中交换左右子节点。
class Solution {public TreeNode invertTree(TreeNode root) {traverse(root);return root;}void traverse(TreeNode root) {if(root null) return ;TreeNode t root.left;root.left root.right;root.right t;traverse(root.left);traverse(root.right);}}二、101. 对称二叉树
题目链接https://leetcode.cn/problems/symmetric-tree/description/ 思路将一个棵二叉树当做两颗二叉树来遍历也就是在递归的函数参数中携带左右两颗子树然后进行比较。
class Solution {public boolean isSymmetric(TreeNode root) {return traverse(root.left, root.right);}boolean traverse(TreeNode node1, TreeNode node2) {if(node1 null node2 null) return true;if(node1 null || node2 null) return false;if(node1.val ! node2.val) return false;return traverse(node1.left, node2.right) traverse(node1.right, node2.left);}}三、104. 二叉树的最大深度
题目链接https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/ 思路后序遍历返回左右子树的最大值即可然后每返回一层就加1即可得到最大深度。
class Solution {public int maxDepth(TreeNode root) {if(root null) return 0;int left maxDepth(root.left);int right maxDepth(root.right);return Math.max(left, right) 1;}
}四、111. 二叉树的最小深度
题目链接https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/ 思路求最小深度需要从上往下找使用前序遍历递归终点为叶子节点到达叶子节点进行判断。
class Solution {int min Integer.MAX_VALUE;public int minDepth(TreeNode root) {if(root null) return 0;traverse(root, 1);return min;}void traverse(TreeNode root, int deep) {if(root null) return;if(root.left null root.right null) {min Math.min(min, deep);return ;}traverse(root.left, deep1);traverse(root.right, deep1);}
}五、222. 完全二叉树的节点个数
题目链接https://leetcode.cn/problems/count-complete-tree-nodes/description/ 思路求完全二叉树的节点个数思路很简单就是利用完全二叉树的性质可以根据深度计算个数所以就前序遍历每一个节点都判断是否是完全二叉树是就不遍历了不是再遍历。
class Solution {public int countNodes(TreeNode root) {if(root null) return 0;int a 0, b 0;TreeNode p root, q root;while(p ! null) {a;p p.left;}while(q ! null) {b;q q.right;}if(a b) return (int)Math.pow(2, a) - 1;return countNodes(root.left) countNodes(root.right) 1;}
}六、110. 平衡二叉树
题目链接https://leetcode.cn/problems/balanced-binary-tree/description/ 思路平衡二叉树是指左右子高度相差不超过1所以直接按照求树的深度就可以解题只要左右深度大于1即不平衡。
class Solution {boolean flag true;public boolean isBalanced(TreeNode root) {traverse(root);return flag;}int traverse(TreeNode root) {if(root null) return 0;int left traverse(root.left);int right traverse(root.right);if(Math.abs(left - right) 1) {flag false;}return Math.max(left, right) 1;}
}七、257. 二叉树的所有路径
题目链接https://leetcode.cn/problems/binary-tree-paths/description/ 思路求所有路径这种题目在回溯中非常常见所以本题也是在递归的过程中使用回溯在叶子节点进行路径组装。
class Solution {ListString result new ArrayList();ListInteger list new ArrayList();public ListString binaryTreePaths(TreeNode root) {traverse(root);return result;}void traverse(TreeNode root) {list.add(root.val);if(root.left null root.right null) {StringBuilder sb new StringBuilder();for(int i : list) {sb.append(i).append(-);}sb.delete(sb.length()-2, sb.length());result.add(sb.toString());return;}if(root.left ! null) {traverse(root.left);list.remove(list.size()-1);}if(root.right ! null) {traverse(root.right);list.remove(list.size()-1);}}
}八、404. 左叶子之和
题目链接https://leetcode.cn/problems/sum-of-left-leaves/description/ 思路求左叶子之和求的是所有的左叶子的和所以只需要做两件事情一件是在叶子节点进行判断另外一件是提供每个节点的信息用于判断当前节点是否是叶子节点这种信息需要从父节点传递所以在递归函数的参数中。
class Solution {int sum 0;public int sumOfLeftLeaves(TreeNode root) {traverse(root, false);return sum;}void traverse(TreeNode root, boolean flag) {if(root null) return ;if(root.left null root.right null flag) {sum root.val;}traverse(root.left, true);traverse(root.right, false);}
}九、513. 找树左下角的值
题目链接https://leetcode.cn/problems/find-bottom-left-tree-value/description/ 思路本题和上一题略有差异上一题是求所有左叶子节点的和要求的是左叶子节点本题类似于树的左视图但是是深度最深的哪一行的最左边的那个节点它可能是左节点也可能是右节点。只需要前序遍历利用深度当深度第一次大于记录值时说明是第一次到达下一层而且采用的是前序遍历到达的是下一层的最左边的叶子节点。
class Solution {int result 0, max 0;public int findBottomLeftValue(TreeNode root) {traverse(root, 1);return result;}void traverse(TreeNode root, int deep) {if(root null) return ;if(root.left null root.right null deep max) {max deep;result root.val;} traverse(root.left, deep 1);traverse(root.right, deep 1);}
}十、112. 路径总和
题目链接https://leetcode.cn/problems/path-sum/description/ 思路求路径总和类似于回溯的用法就是在树的递归过程中使用回溯如果是全局变量需要手动回滚数据如果是携带是函数参数列表则不需要。
class Solution {boolean flag false;public boolean hasPathSum(TreeNode root, int targetSum) {traverse(root, targetSum, 0);return flag;}void traverse(TreeNode root, int targetSum, int sum) {if(root null || flag) return;sum root.val;if(root.left null root.right null) {if(sum targetSum) flag true;}traverse(root.left, targetSum, sum);traverse(root.right, targetSum, sum);}
}
