力扣爆刷第115天之CodeTop100五连刷61-65

本文主要是介绍力扣爆刷第115天之CodeTop100五连刷61-65，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣爆刷第115天之CodeTop100五连刷61-65

一、32. 最长有效括号

题目链接：https://leetcode.cn/problems/longest-valid-parentheses/description/
思路：使用栈，栈内存索引，遇到左括号，入栈，遇到右括号出栈，故栈底要初始化一个值，来满足计算括号长度，举例()，可以压入-1，左括号再压入0，右括号来了，0出栈，i= 1，减去栈顶的-1，长度为2，初始化验证完毕。每次出栈更新max，另外注意边界条件。

class Solution {public int longestValidParentheses(String s) {LinkedList<Integer> stack = new LinkedList<>();int max = 0;stack.push(-1);for(int i = 0; i < s.length(); i++) {if(s.charAt(i) == '(') {stack.push(i);}else{stack.pop();if(stack.isEmpty()) {stack.push(i);}else{max = Math.max(max, i - stack.peek());}}}return max;}
}

二、129. 求根节点到叶节点数字之和

题目链接：https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/
思路：使用回溯的思想，前序遍历，收集数字，抵达叶子节点即到达回溯的最深层，计算加和。然后是左右子树遍历，然后是回溯返回。

class Solution {int sum = 0;StringBuilder builder = new StringBuilder();public int sumNumbers(TreeNode root) {traverse(root);return sum;}void traverse(TreeNode root) {if(root == null) return;builder.append(root.val);if(root.left == null && root.right == null) {sum += Integer.valueOf(builder.toString());}traverse(root.left);traverse(root.right);builder.deleteCharAt(builder.length()-1);}}

三、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;}
}

四、101. 对称二叉树

题目链接：https://leetcode.cn/problems/symmetric-tree/description/
思路：就是从根节点开始把一颗二叉树分成两个二叉树，然后前序遍历，递归比较即可。

class Solution {public boolean isSymmetric(TreeNode root) {return traverse(root.left, root.right);}boolean traverse(TreeNode t1, TreeNode t2) {if(t1 == null && t2 == null) return true;if(t1 != null && t2 != null) {if(t1.val != t2.val) return false;boolean left = traverse(t1.left, t2.right);boolean right = traverse(t1.right, t2.left);return left && right;}return false;}
}

五、110. 平衡二叉树

题目链接：https://leetcode.cn/problems/balanced-binary-tree/description/
思路：判断是否是二叉树，关键在于每个节点的左右子树高度差不能大于1，所以一直后序遍历求深度，在其过程中判断是否非法，非法记录全局变量，即可，另外可以早停利用全局变量。

class Solution {boolean flag = true;public boolean isBalanced(TreeNode root) {traverse(root);return flag;}int traverse(TreeNode root) {if(root == null || !flag) 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;}
}

这篇关于力扣爆刷第115天之CodeTop100五连刷61-65的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---