前言

代码随想录算法训练营day17

一、Leetcode 110.平衡二叉树

1.题目

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4] 输出：false

示例 3：

输入：root = [] 输出：true

提示：

1. 树中的节点数在范围 [0, 5000] 内
2. -104 <= Node.val <= 104

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/balanced-binary-tree

2.解题思路

解题思路

方法一：自顶向下的递归

定义函数 heightheight，用于计算二叉树中的任意一个节点 pp 的高度：

height(p)={0p 是空节点max⁡(height(p.left),height(p.right))+1p 是非空节点height(p)={0max(height(p.left),height(p.right))+1p 是空节点p 是非空节点

有了计算节点高度的函数，即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 11，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

3.代码实现

```java class Solution { public boolean isBalanced(TreeNode root) { if (root == null) { return true; } else { return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } }

1. public int height(TreeNode root) {
2. if (root == null) {
3. return 0;
4.     } else {
5. return Math.max(height(root.left), height(root.right)) + 1;
6.     }
7. }

}

```

二、Leetcode 257. 二叉树的所有路径

1.题目

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]

示例 2：

输入：root = [1] 输出：["1"]

提示：

1. 树中节点的数目在范围 [1, 100] 内
2. -100 <= Node.val <= 100

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/binary-tree-paths

2.解题思路

方法一：深度优先搜索

思路与算法

最直观的方法是使用深度优先搜索。在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。

1. 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
2. 如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案即可。

如此，当遍历完整棵二叉树以后我们就得到了所有从根节点到叶子节点的路径。当然，深度优先搜索也可以使用非递归的方式实现，这里不再赘述。

3.代码实现

```java class Solution { public List binaryTreePaths(TreeNode root) { List paths = new ArrayList (); constructPaths(root, "", paths); return paths; }

1. public void constructPaths(TreeNode root, String path, List<String> paths) {
2. if (root != null) {
3.         StringBuffer pathSB = new StringBuffer(path);
4.         pathSB.append(Integer.toString(root.val));
5. if (root.left == null && root.right == null) {  // 当前节点是叶子节点
6.             paths.add(pathSB.toString());  // 把路径加入到答案中
7.         } else {
8.             pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
9.             constructPaths(root.left, pathSB.toString(), paths);
10.             constructPaths(root.right, pathSB.toString(), paths);
11.         }
12.     }
13. }

}

```

三、Leetcode 404.左叶子之和 v

1.题目

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1] 输出: 0

提示:

1. 节点数在 [1, 1000] 范围内
2. -1000 <= Node.val <= 1000

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/sum-of-left-leaves

2.解题思路

方法一：深度优先搜索

3.代码实现

```java class Solution { public int sumOfLeftLeaves(TreeNode root) { return root != null ? dfs(root) : 0; }

1. public int dfs(TreeNode node) {
2.     int ans = 0;
3. if (node.left != null) {
4.         ans += isLeafNode(node.left) ? node.left.val : dfs(node.left);
5.     }
6. if (node.right != null && !isLeafNode(node.right)) {
7.         ans += dfs(node.right);
8.     }
9. return ans;
10. }
11. 
12. public boolean isLeafNode(TreeNode node) {
13. return node.left == null && node.right == null;
14. }

}

```