代码随想录day15| 110.平衡二叉树 、 257. 二叉树的所有路径 、 404.左叶子之和、 222.完全二叉树的节点个数

110.平衡二叉树

思路

递归后序遍历（知道左右子树的结果才能确定当前根节点的性质）， 左子树的深度和右子树的深度相差是否大于一，如果大于一则返回-1，否则返回当前节点深度

class Solution {public boolean isBalanced(TreeNode root) {if(getDepth(root) == -1){return false;}return true;}public int getDepth(TreeNode root) {if(root == null){return 0;}int m = getDepth(root.left);int n = getDepth(root.right);if(m ==-1 ||n == -1){return -1;}else if(Math.abs(m-n) > 1){return -1;}else{return 1+Math.max(m,n);}}
}

257. 二叉树的所有路径

思路

使用前序遍历+回溯来收集路径

class Solution {public List<String> binaryTreePaths(TreeNode root) {List<Integer> list1 = new LinkedList();List<String> list = new ArrayList();getPath(root, list1, list);return list;}public void getPath(TreeNode root, List<Integer> list1, List list) {list1.add(root.val);if(root.left == null && root.right == null){String s = listToString(list1);list.add(s);return ;}if(root.left != null){getPath(root.left, list1, list);list1.remove(list1.size()-1);}if(root.right != null){getPath(root.right, list1, list);list1.remove(list1.size()-1);}}public String  listToString(List<Integer> list1){StringBuffer s = new StringBuffer();s.append(list1.get(0));for(int i = 1 ; i < list1.size() ; i++){s.append("->");s.append(list1.get(i)); }return s.toString();}
}

404.左叶子之和

思路

使用后序遍历，收集左子树和右子树中左叶子节点的和

class Solution {public int sumOfLeftLeaves(TreeNode root) {int sum = 0;return getSunLeft(root);}public int getSunLeft(TreeNode root) {if(root == null){return 0;}if(root.left == null && root.right == null){return 0;}int left = getSunLeft(root.left);int right = getSunLeft(root.right);if(root.left != null && root.left.left ==null && root.left.right == null){  left = root.left.val;}return left+right;}
}

222.完全二叉树的节点个数

使用递归（中序）记录节点个数

class Solution {public int countNodes(TreeNode root) {int sum = 0;if(root == null){return 0;}return count(root, sum);}public int count(TreeNode root, int sum) {if(root.left == null && root.right == null){return sum+=1;}if(root.left != null){sum = count(root.left, sum);}sum += 1;if(root.right != null){sum = count(root.right, sum);}return sum;}
}