力扣爆刷第159天之TOP100五连刷61-65（翻转单词、对称二叉树、遍历求和）

力扣爆刷第159天之TOP100五连刷61-65（翻转单词、对称二叉树、遍历求和）

一、151. 反转字符串中的单词

题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/description/
思路：很经典的题目，翻转字符串中的单词，只需要把所有单词都翻转，然后再整体翻转就可以。具体的实现方式有很多，比如用stringbuilder拼接然后翻转的，也有用集合收集之后翻转的，都可以。

class Solution {public String reverseWords(String s) {StringBuilder sb = new StringBuilder();StringBuilder temp = new StringBuilder();for(char c : s.toCharArray()) {if(c != ' ') temp.append(c);else if(temp.length() > 0) {sb.append(temp.reverse()).append(' ');temp = new StringBuilder();}}if(temp.length() != 0) sb.append(temp.reverse());if(sb.charAt(sb.length()-1)  == ' ') sb.deleteCharAt(sb.length()-1);return sb.reverse().toString();}}

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

题目链接：https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/
思路：本题怎么都可以做，求的是从根节点到叶子节点的每一条通路都是一个数，这个数是从根节点拼接到叶子节点的。所以可以使用前序遍历，但是又要注意回溯返回，有回溯的思想在里面。其他的就没有了。

class Solution {int sum = 0;public int sumNumbers(TreeNode root) {backTracking(root, 0);return sum;}void backTracking(TreeNode root, int temp) {if(root == null) return;temp = root.val + temp * 10;if(root.left == null && root.right == null) {sum += temp;}backTracking(root.left, temp);backTracking(root.right, temp);}}

三、104. 二叉树的最大深度

题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
思路：求最大深度，没啥好说的经典后序遍历，返回左右子树的最大深度作为最大深度。

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 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);}}

五、144. 二叉树的前序遍历

题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
思路：这个就是前序遍历收集，没啥可说的。

class Solution {List<Integer> list = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {if(root == null) return list;list.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return list;}
}