代码随想录算法训练营二十四期第十七天|LeetCode110. 平衡二叉树、LeetCode257. 二叉树的所有路径、LeetCode404. 左叶子之和

本文主要是介绍代码随想录算法训练营二十四期第十七天|LeetCode110. 平衡二叉树、LeetCode257. 二叉树的所有路径、LeetCode404. 左叶子之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、LeetCode110. 平衡二叉树

题目链接：110. 平衡二叉树

利用函数递归，分别计算出左右子树的高度，然后判断做右子树的高度差是否大于1，如果大于1，返回-1，表明该树不是二叉树，否则返回做右子树的高度最大值加一。

代码如下：

class Solution {public int maxDepth(TreeNode root) {if(root == null) return 0;//如果当前节点为空，返回当前高度0int leftHigh = maxDepth(root.left);//如果有左子树，返回左子树的高度if(leftHigh == -1) return -1;//用-1标记概述已经不是平衡二叉树int rightHight = maxDepth(root.right);//如果有右子树，返回右子树的高度if(rightHight == -1) return -1;return Math.abs(leftHigh - rightHight) > 1 ? -1 : (rightHight > leftHigh ? rightHight + 1 : leftHigh + 1);//如果做右子树的高度差大于1，返回-1表示该树不是平衡二叉树，否则返回做右子树的最大高度加一}public boolean isBalanced(TreeNode root) {return maxDepth(root) == -1 ? false : true;//函数如果返回的是-1说明不是平衡二叉树，否则是平衡二叉树}
}

二、LeetCode257. 二叉树的所有路径

题目链接：257. 二叉树的所有路径

先处理头节点（头节点是所有路径的开头，直接添加到路径字符串当中），然后通过递归方法遍历每一条路径，找到叶子节点时，将路径放到外部定义的一个结果集当中。最后将结果集返回即可。

具体代码如下：

class Solution {List<String> arr = new ArrayList<String>();public void travelRoad(TreeNode root, String road) {if(root.left == null && root.right == null) {//找到叶子节点，将路径放到结果集，返回arr.add(road);return;}if(root.left != null) {//如果左节点不为空，将左节点放入路径上travelRoad(root.left, road + "->" + Integer.toString(root.left.val));}if(root.right != null) {//如果右节点不为空将右节点放到路径travelRoad(root.right, road + "->" + Integer.toString(root.right.val));}}public List<String> binaryTreePaths(TreeNode root) {String s = Integer.toString(root.val);//先处理头节点，将头节点的值放入路径，头节点为所有路径的开头travelRoad(root, s);return arr;}
}

三、LeetCode404. 左叶子之和

题目链接：404. 左叶子之和

通过递归分别算出左右子树的左叶子节点的总和。

还要考虑左子节点是左叶子节点的情况。

最后将三者相加返回即可。

代码如下：

class Solution {public int sumOfLeftLeaves(TreeNode root) {int leftCount = 0;//如果有左叶子节点，记录左叶子节点的值if(root.left != null && root.left.left == null && root.left.right == null) {leftCount = root.left.val;}int leftSum = 0;//记录左子树的做叶子节点的总和int rightSum = 0;//记录右子树的左叶子节点值的总和if(root.left != null) leftSum = sumOfLeftLeaves(root.left);//通过递归函数计算左子树的做叶子节点和if(root.right != null) rightSum = sumOfLeftLeaves(root.right);//计算右子树的左叶子节点和return leftSum + rightSum + leftCount;//返回左子树的做叶子节点和加上右子树的左叶子节点的和再加上。}
}