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

一、LeetCode110. 平衡二叉树

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

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

代码如下：

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;//如果当前节点为空，返回当前高度0
        int 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;//返回左子树的做叶子节点和加上右子树的左叶子节点的和再加上。
    }
}

总结

递归二叉树。