训练营第十七天（二叉树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;
		else
			return 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)

题目

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

示例：

解答

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

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

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);
    }
}