网站公司备案通知,百度seo文章,wordpress企業主题,海拉尔网站建设+网站设计文章目录 Day 17 第六章 二叉树part04110.平衡二叉树 #xff08;优先掌握递归#xff09;基础递归思路递归代码 257. 二叉树的所有路径 #xff08;优先掌握递归#xff09;递归思路递归代码 404.左叶子之和 #xff08;优先掌握递归#xff09;思路自己的思路#xff… 文章目录 Day 17 第六章 二叉树part04110.平衡二叉树 优先掌握递归基础递归思路递归代码 257. 二叉树的所有路径 优先掌握递归递归思路递归代码 404.左叶子之和 优先掌握递归思路自己的思路✅通过随想录代码 Day 17 第六章 二叉树part04
今日内容 ● 110.平衡二叉树● 257. 二叉树的所有路径● 404.左叶子之和迭代法大家可以直接过二刷有精力的时候 再去掌握迭代法。
110.平衡二叉树 优先掌握递归 再一次涉及到什么是高度什么是深度可以巩固一下。题目链接https://leetcode.cn/problems/balanced-binary-tree视频讲解https://www.bilibili.com/video/BV1Ug411S7my文章讲解https://programmercarl.com/0110.%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91.html 基础
二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。 求深度从上到下前序遍历中左右 二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。 求高度从下到上后序遍历左右中
递归思路
因为平衡二叉树的概念是每个节点的左右子树高度差的绝对值不大于1所以就可以比较每个节点左右子树的高度所以使用后序遍历
确定递归函数的参数和返回值 参数节点返回值返回当前节点的高度但当从该节点就能看出不是平衡二叉树则返回-1 确定终止条件 终止条件传入节点为空返回0 确定单层递归的逻辑 获取左子树高度获取右子树高度差大于一返回-1小于一返回最大高度1
递归代码
public static boolean isBalanced(TreeNode root) {return getHeight(root) ! -1;
}
public static int getHeight(TreeNode root){//当节点为空返回0高度为0if(root null) return 0;//先得到左子树的高度int left getHeight(root.left);//如果是-1直接不是平衡二叉树了if(left -1) return -1;//再得到右子树的高度int right getHeight(root.right);if(right -1) return -1;if(Math.abs(left - right) 1) return -1;else return Math.max(left, right) 1;
}257. 二叉树的所有路径 优先掌握递归 这是大家第一次接触到回溯的过程 我在视频里重点讲解了 本题为什么要有回溯已经回溯的过程。如果对回溯 似懂非懂没关系 可以先有个印象。题目链接https://leetcode.cn/problems/binary-tree-paths/视频讲解https://www.bilibili.com/video/BV1ZG411G7Dh文章讲解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 递归思路
从上到下找路径。所以使用前序遍历
确定递归函数的参数和返回值 参数节点pathres path存储单条路径res存储结果放path的集合 返回值不用返回void 确定终止条件 终止条件传入节点为空返回 确定单层递归的逻辑
递归代码
public static ListString binaryTreePaths(TreeNode root) {LinkedListString res new LinkedList();getPath(root, , res);return res;
}
public static void getPath(TreeNode root, String path, LinkedListString res){//如果节点为空返回if(root null) return;//如果是叶子结点就把当前的path和val加入resif(root.left null root.right null){res.add(path root.val);return;}//当该节点不是叶子节点把val-加入path递归getPath(root.left, path root.val -, res);getPath(root.right, path root.val -, res);
}404.左叶子之和 优先掌握递归 其实本题有点文字游戏搞清楚什么是左叶子剩下的就是二叉树的基本操作。题目链接https://leetcode.cn/problems/sum-of-left-leaves/视频讲解https://www.bilibili.com/video/BV1GY4y1K7z8文章讲解https://programmercarl.com/0404.%E5%B7%A6%E5%8F%B6%E5%AD%90%E4%B9%8B%E5%92%8C.html 思路
精准踩雷没看清是左叶子以为是所有左节点 另一个疑问为啥不能用int类型直接加哦应该用返回不能作为参数
自己的思路✅通过
public static int sumOfLeftLeaves(TreeNode root) {int sum 0;ArrayListInteger res new ArrayList();dfs(root, res);for(int i : res){sum i;}return sum;
}
public static void dfs(TreeNode root, ArrayListInteger res){if(root null) return;if(root.left ! null root.left.right null root.left.left null) res.add(root.left.val);dfs(root.left, res);dfs(root.right, res);System.out.println(res);
}随想录代码
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;
}
