今日内容:
● 110.平衡二叉树
● 257. 二叉树的所有路径
● 404.左叶子之和
详细布置
迭代法,直接过,二刷有精力的时候 再去掌握迭代法。
110.平衡二叉树 (优先掌握递归)
题目链接/文章讲解/视频讲解:https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
思路:递归
- 递归函数的参数和返回值:参数:当前传入节点。
返回值:传入节点为根节点的树的高度。若已不是平衡二叉树,返回-1 - 递归出口: root == null
- 单层处理逻辑:分别求出其左右子树的高度,然后如果差值小于等于1,则返回当前二叉树的高度,否则则返回-1,表示已经不是二叉平衡树。
class Solution { /** * 递归法 */ public boolean isBalanced(TreeNode root) { return getHeight(root) != -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,return -1表示已经不是平衡树了 if (Math.abs(leftHeight - rightHeight) > 1) { return -1; } return Math.max(leftHeight, rightHeight) + 1; } }
257. 二叉树的所有路径 (优先掌握递归)
这是大家第一次接触到回溯的过程, 我在视频里重点讲解了 本题为什么要有回溯,已经回溯的过程。
如果对回溯 似懂非懂,没关系, 可以先有个印象。
题目链接/文章讲解/视频讲解:https://programmercarl.com/0257.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%89%80%E6%9C%89%E8%B7%AF%E5%BE%84.html
递归:
1.递归函数的参数和返回值
2.确定递归
3.确定单层递归逻辑
class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res = new ArrayList<>(); if (root == null){ return res; } ArrayList<Integer> paths = new ArrayList<>(); traversal(root,paths,res); return res; } private void traversal(TreeNode root, List<Integer> paths, List<String> res) { paths.add(root.val); // 叶子结点 if (root.left == null && root.right == null) { // 输出 StringBuilder sb = new StringBuilder(); for (int i = 0; i < paths.size() - 1; i++) { sb.append(paths.get(i)).append("->"); } sb.append(paths.get(paths.size() - 1)); res.add(sb.toString()); return; } if (root.left != null) { traversal(root.left, paths, res); paths.remove(paths.size() - 1);// 回溯 } if (root.right != null) { traversal(root.right, paths, res); paths.remove(paths.size() - 1);// 回溯 } } }
404.左叶子之和 (优先掌握递归)
其实本题有点文字游戏,搞清楚什么是左叶子,剩下的就是二叉树的基本操作。
题目链接/文章讲解/视频讲解:https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html
class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) { return 0; } int leftValue = sumOfLeftLeaves(root.left); int rightValue = sumOfLeftLeaves(root.right); int midValue = 0; if (root.left != null && root.left.left == null && root.left.right == null) { midValue = root.left.val; } int sum = midValue + leftValue + rightValue; return sum; } }标签:paths,return,随想录,404,二叉树,null,root,left From: https://www.cnblogs.com/gaoyuan2lty/p/17048297.html