力扣爆刷第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;}
}