训练营第十七天（二叉树part04）

本文主要是介绍训练营第十七天（二叉树part04），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第十七天二叉树part04

110.平衡二叉树

力扣题目链接(opens new window)

题目

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

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

在这里插入图片描述

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

在这里插入图片描述

返回 false 。

解答

求深度，后序遍历

左子树如果不是平衡二叉树，没有继续的必要，直接结束
右子树如果不是平衡二叉树，同样也没有继续的必要
最后如果左右子树高度差距大于1，也就结束，不是平衡二叉树，否则就继续

class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;//-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;//如果左右子树高度差距大于1，也就结束if (Math.abs(leftHeight - rightHeight) > 1)return -1;elsereturn Math.max(leftHeight,rightHeight) + 1;}
}

257. 二叉树的所有路径

力扣题目链接(opens new window)

题目

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

在这里插入图片描述

解答

注意进行回溯，不然无法寻找第二条路径，每次递归就会回溯一次

class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();// 存最终的结果if (root == null) {return res;}List<Integer> path = new ArrayList<>();// 作为结果中的路径traversal(root, path, res);return res;}private void traversal(TreeNode root, List<Integer> path, List<String> res){path.add(root.val);//必须放在if前，不然直接到叶子节点会结束，叶子结点的值不会放到path里面if (root.left == null && root.right == null){//到了叶子StringBuilder sb = new StringBuilder();for (int i = 0; i < path.size() - 1; i++) {sb.append(path.get(i)).append("->");}sb.append(path.get(path.size() - 1));// 记录最后一个节点res.add(sb.toString());// 收集一个路径return;}if (root.left != null) { // 左traversal(root.left, path, res);path.remove(path.size() - 1);// 进行回溯，移除最下面的元素//因为当前会找到下一级结点，直接递归到叶子结点，那么进行递归回溯后，每次移除一个，才能更新path}if (root.right != null) { // 右traversal(root.right, path, res);path.remove(path.size() - 1);// 进行回溯，移除最下面的元素}}
}

404.左叶子之和

力扣题目链接(opens new window)

题目

计算给定二叉树的所有左叶子之和。

示例：

在这里插入图片描述

解答

对于递归树，只可能出现两个情况

当前的结点的左子树是左叶子，那么最终值为左叶子值+右子树的结果
左子树不是左叶子，最终值为左子树的结果+右子树的结果

class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null)return 0;TreeNode left = root.left;if (left != null && left.left == null && left.right == null)return left.val + sumOfLeftLeaves(root.right);return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);}
}