【算法第十三天7.27】平衡二叉树，二叉树所有路径，左叶子之和

链接力扣110-平衡二叉树

思路
1、左右子树高度差不超过1

2、左子树、右子树均为平衡二叉树

3、需要获得树高，如果不是平衡的就返回-1；如果是平衡，就返回对应的高

class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) == -1 ? false:true;}public int getHeight(TreeNode root){if(root == null) return 0;int leftHeight = getHeight(root.left);// 如果左树不平衡if(leftHeight == -1) return -1;int rightHeight = getHeight(root.right);// 如果右树不平衡if(rightHeight == -1) return -1;return Math.abs(leftHeight - rightHeight) > 1 ? -1:1 + Math.max(leftHeight,rightHeight);}
}

链接力扣257- 二叉树的所有路径

思路
1、首先需要将这条路径上的值收集到集合里；

2、将集合里的值取出来，加上 -> 串成String，这里需要注意，最后一个结节的处理与前面不同，需要单独处理，只加值即可；（这里需要用到StringBuilder）

3、将遍历好的路径加到res集合中，此时需要回溯，将最后一个结点值删除，再去遍历得到下一条路径

前、中、后遍历

class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();if (root == null) {return res;}List<Integer> path = new ArrayList<>();traversal(root, path, res);return res;}// 记录每一条路径的path值（之后再转为字符串）、存放结果的respublic void traversal(TreeNode root,List<Integer> path,List<String> res){// 1、逻辑是前序遍历，需要先处理中间节点path.add(root.val);// 2、处理左右孩子节点// 左右结点都为空，就到了叶子节点位置if(root.left == null && root.right == null){// 因为结果数组里的每个元素是字符串StringBuilder tmp = new StringBuilder();// 最后一个值的处理逻辑跟前面不同，不需要 ->for(int i = 0; i < path.size() - 1; i++){tmp.append(path.get(i)).append("->");}// 单独处理最后一个结点值tmp.append(path.get(path.size()-1));res.add(tmp.toString());// 到这里结束这一次的traversalreturn;}if(root.left != null){// traversal一次，会得到一条路径，但是想要得到下一条路径，需要回溯到上一节点，// 这时，需要将path集合中的最后一个结节值删除traversal(root.left,path,res);path.remove(path.size() - 1);}if(root.right != null){traversal(root.right,path,res);path.remove(path.size() -1);}}
}

链接力扣404. 左叶子之和

思路
1、如何判断是左叶子：
root.left 还不行，需要 root.left.left == null && root.left.right ==null
此时：leftValue 就是 root.left.val

2、如果是左子树，右子树（下面还有子树），则继续递归，每次左子树时，都需要判断是否是左叶子

class Solution {// 定义全局变量以便后面相加使用int res = 0;public int sumOfLeftLeaves(TreeNode root){if(root == null) return 0;if(root.left != null && root.left.left == null && root.left.right == null){res += root.left.val;}sumOfLeftLeaves(root.left);sumOfLeftLeaves(root.right);return res;}
}