算法训练营day17(二叉树04:平衡二叉树,所有路径,左叶子和)
第六章 二叉树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/DUHBQRm1aSWR4T2NKday17
平衡二叉树
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博客