代码随想录算法训练营Day17|404.左叶子之和 110.平衡二叉树 222.完全二叉树的节点个数

本文主要是介绍代码随想录算法训练营Day17|404.左叶子之和 110.平衡二叉树 222.完全二叉树的节点个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

404.左叶子之和

在这里插入图片描述
1、这道题需要统计出所有左叶子结点的值的和，首先要明确左叶子节点指的左右孩子节点均为null的左节点。如上图就是4和6.
2.但是光凭叶子结点本身是无法判定左叶子的，因为左右孩子都是null，所以要从上一层节点往下判定。所以判断左叶子的条件语句应该是 root.left != null && root.left.leftnull && root.left.rightnull
3.另外，这道题目采用后序遍历是最方便的。并且要明确递归三要素：返回值、终止条件、递归逻辑。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int sumOfLeftLeaves(TreeNode root) {return getSum(root);}public int getSum(TreeNode root){//终止条件if(root == null) return 0;if(root.left == null && root.right==null) return 0;//递归逻辑//左int leftSum = getSum(root.left);//左子树的条件if(root.left != null && root.left.left == null && root.left.right == null) leftSum += root.left.val;//右int rightSum = getSum(root.right);//中int sum = leftSum + rightSum;return sum;}
}

110.平衡二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isBalanced(TreeNode root) {return getDepth(root)==-1?false:true;}//三要素：1、返回值 2、终止条件 3、递归逻辑//如果不为平衡二叉树，返回-1public int getDepth(TreeNode root){if(root == null) return 0;int leftHeight = getDepth(root.left);if(leftHeight == -1) return -1;int rightHeight = getDepth(root.right);if(rightHeight == -1) return -1;if(Math.abs(leftHeight-rightHeight) > 1) return -1;else return Math.max(leftHeight,rightHeight)+1;}
}

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

这道题利用了递归和回溯的思想，进入到左子树的递归体对path完成相应的操作之后，在回到主函数中需要将操作的那个值再删除，再进入右子树的递归体。而一旦遇到叶子结点，就是收获结果的时候，要将这个结果加入到res中。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<String> binaryTreePaths(TreeNode root) {ArrayList<String> res = new ArrayList<String>();ArrayList<Integer> path = new ArrayList<Integer>();//用列表存需要回溯的值buildPaths(root,path,res);return res;}public void buildPaths(TreeNode root,List<Integer> path,List<String> res){//中，这样避免遗漏叶子结点path.add(root.val);if(root.left == null && root.right == null){//如果左右节点都为空此时要将path中的值转为String放入res中res.add(pathToString(path));return;}//左if(root.left != null){buildPaths(root.left,path,res);int len = path.size();path.remove(len-1);}//右if(root.right != null){buildPaths(root.right,path,res);int len = path.size();path.remove(len-1);}}public String pathToString(List<Integer> path){int size = path.size();StringBuilder str = new StringBuilder();for(int i = 0;i < size-1;i++){str.append(path.get(i)+"->");}str.append(path.get(size-1));return str.toString();}
}