day17-二叉树part04
110.平衡二叉树 （优先掌握递归）后序遍历 左右中
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}//递归三部曲 确定方法的参数与返回值private 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;}//比较左右子树高度差 如果大于一直接返回不是平衡二叉树if(Math.abs(leftHeight - rightHeight) > 1){return -1;}return Math.max(leftHeight,rightHeight) + 1;}
}257. 二叉树的所有路径 （优先掌握递归） 前序遍历 根左右
class Solution {//根节点到叶子节点的所有路径 前序遍历先获取根节点public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>(); //最终结果if(root == null){return res;}//结果中的路径 List<Integer> paths = new ArrayList<>();traversal(root,paths,res);return res;}private void traversal(TreeNode root,List<Integer> paths,List<String> res){paths.add(root.val);//终止条件if(root.left == null && root.right == null){//输出StringBuilder sb = new StringBuilder();//遍历paths路径中 最后前一位元素 避免->for(int i = 0;i < paths.size()-1;i++){sb.append(paths.get(i)).append("->");}sb.append(paths.get(paths.size() -1 )); //记录最后一个路径res.add(sb.toString()); //收集一条路径return;}//单层递归逻辑//左if(root.left != null){traversal(root.left,paths,res);//下一个节点完成 回溯paths.remove(paths.size() -1); }//右if(root.right != null){traversal(root.right,paths,res);paths.remove(paths.size() -1);}}
}404.左叶子之和 （优先掌握递归）
左叶子定义:节点A的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么A节点的左孩子为左叶子节点
class Solution {//后序遍历 左右中public int sumOfLeftLeaves(TreeNode root) {if(root == null){return 0;}if(root.left == null && root.right == null) return 0;int leftVaule = sumOfLeftLeaves(root.left); //左if(root.left != null && root.left.left == null && root.left.right == null){ // 左子树就是一个左叶子的情况leftVaule = root.left.val;}int rightValue = sumOfLeftLeaves(root.right); //右int sum =leftVaule + rightValue; //中return sum;}
}