第六章 二叉树part04今日内容: ● 110.平衡二叉树
● 257. 二叉树的所有路径
● 404.左叶子之和 详细布置 迭代法,大家可以直接过,二刷有精力的时候 再去掌握迭代法。110.平衡二叉树 (优先掌握递归)再一次涉及到,什么是高度,什么是深度,可以巩固一下。题目链接/文章讲解/视频讲解:https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html 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 404.左叶子之和 (优先掌握递归)其实本题有点文字游戏,搞清楚什么是左叶子,剩下的就是二叉树的基本操作。 题目链接/文章讲解/视频讲解:https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html 往日任务
● day 1 任务以及具体安排:https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排:https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排:https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排:https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 周日休息
● day 6 任务以及具体安排:https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排:https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排:https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
● day 9 任务以及具体安排:https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
● day 10 任务以及具体安排:https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排:https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 周日休息
●day 13 任务以及具体安排:https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排:https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排:https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv
●day 16 任务以及具体安排:https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK
day17
平衡二叉树
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;}public 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;}if( Math.abs(leftHeight - rightHeight) > 1){return -1;}return Math.max(leftHeight, rightHeight) + 1;}}
二叉树的所有路径
递归法(涉及到回溯)
StringBuilder可以append(),toString();
List可以add,get(index),removeLast();
//paths保持了从根节点到当前节点的路径。//每当递归深入时,我们将当前节点的值添加到paths中,每一层递归在返回的时候都有一层remove;class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> res = new ArrayList<>();//结果集List<Integer> path = new ArrayList<>();//每条路径getPath(root, path, res);return res;}private void getPath(TreeNode root, List<Integer> path, List<String> res){//出递归path.add(root.val);//前序遍历,结果不遍历空节点,所以出递归前先加进去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){getPath(root.left, path, res);path.removeLast();//每次的一个递归进去,再出来的时候都要把递归里面添加的点去掉}if( root.right != null){getPath(root.right, path, res);path.removeLast();}}}
左叶子之和
递归法
确定每个节点的左叶子数量,所以是把自己当做父节点的视角去判断的,故判断条件为root.left != null && root.left.left == null && root.left.right == null
后序遍历,左右子树处理完之后给父节点
class Solution {public int sumOfLeftLeaves(TreeNode root) {//后序遍历if( root == null) return 0;if( root.left == null && root.right == null) return 0;//遇到叶子结点,叶子结点的左子结点必为0//不加这行也行,反正叶子没必要处理int leftNum = sumOfLeftLeaves(root.left); if( root.left != null && root.left.left == null && root.left.right == null) {//遇到左叶子leftNum = root.left.val;}int rightNum = sumOfLeftLeaves(root.right);return leftNum + rightNum;}}
感谢大佬分享:
代码随想录-算法训练营day17【二叉树04:平衡二叉树、二叉树的所有路径、左叶子之和】-CSDN博客