网站 空间 购买,国际新闻最新消息今天新闻大事件 中方,网页入口网站推广,深圳网站建设者文章目录 1.【110】平衡二叉树#xff08;优先掌握递归#xff09;1.1 题目描述1.2 解题思路1.3 java代码实现 2.【257】二叉树的所有路径#xff08;优先掌握递归#xff09;2.1 题目描述2.2 解题思路2.3 java代码实现 3.【404】左叶子之和#xff08;优先掌握递归#… 文章目录 1.【110】平衡二叉树优先掌握递归1.1 题目描述1.2 解题思路1.3 java代码实现 2.【257】二叉树的所有路径优先掌握递归2.1 题目描述2.2 解题思路2.3 java代码实现 3.【404】左叶子之和优先掌握递归3.1 题目描述3.2 解题思路3.3 java代码实现 【110】平衡二叉树 【257】二叉树的所有路径 【404】左叶子之和 1.【110】平衡二叉树优先掌握递归
【110】平衡二叉树
1.1 题目描述
给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 提示
树中的节点数在范围 [0, 5000] 内-104 Node.val 104
1.2 解题思路
做这道题目时我们需要再明确一下二叉树节点的深度和高度
二叉树节点的深度指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数。前序求深度后序求高度。 既然让比较高度那么要用后序遍历。 递归三部曲 明确递归函数的参数和返回值
参数当前传入节点 返回值以当前传入节点为根节点的树的高度
public int getHeight(TreeNode node){明确终止条件
递归的过程中依然是遇到空节点了为终止返回0表示当前节点为根节点的树高度为0 if (nodenull){return 0;}明确单层递归的逻辑
如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢当然是其左子树高度和其右子树高度的差值。
分别求出其左右子树的高度然后如果差值小于等于1则返回当前二叉树的高度否则返回-1表示已经不是二叉平衡树了。 int leftHeightgetHeight(node.left);//左if (leftHeight-1){return -1;}int rightHeightgetHeight(node.right);//右if (rightHeight-1){return -1;}//我们已经把不符合平衡树的条件去除了//接下来就是符合平衡树的条件了//那么就要计算左右子树的高度差了int result;if (Math.abs(leftHeight-rightHeight)1){//根result-1;}else {//以当前节点为根节点的树的最大高度result1Math.max(leftHeight,rightHeight);}return result;1.3 java代码实现
class Solution {public boolean isBalanced(TreeNode root) {return getHeight(root) -1 ?false:true;}public int getHeight(TreeNode node){if (nodenull){return 0;}int leftHeightgetHeight(node.left);//左if (leftHeight-1){return -1;}int rightHeightgetHeight(node.right);//右if (rightHeight-1){return -1;}/*int result;if (Math.abs(leftHeight-rightHeight)1){//根result-1;}else {//以当前节点为根节点的树的最大高度result1Math.max(leftHeight,rightHeight);}return result;*///上面代码简化一下return Math.abs(leftHeight-rightHeight)1?-1:1Math.max(leftHeight,rightHeight);}
}2.【257】二叉树的所有路径优先掌握递归
【257】二叉树的所有路径
2.1 题目描述
给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。 提示
树中节点的数目在范围 [1, 100] 内-100 Node.val 100
2.2 解题思路
第一次在二叉树中接触到回溯关于本题的详解可以看一下卡哥的视频视频讲解的很清楚。
递归中带着回溯你感受到了没| LeetCode257. 二叉树的所有路径
这道题目要求从根节点到叶子的路径所以需要前序遍历这样才方便让父节点指向孩子节点找到对应的路径。
在这道题目中将第一次涉及到回溯因为我们要把路径记录下来需要回溯来回退一个路径再进入另一个路径。
前序遍历以及回溯的过程如图 要知道递归和回溯是一家的本题使用递归的方式也需要回溯。 递归三部曲 确定递归函数的参数以及返回值
要传入根节点记录每一条路径的path和存放结果集的result这里的递归不需要返回值。
public void traversal(TreeNode root, ListInteger paths,ListString result)确定终止条件
当我们遍历到叶子结点时就该返回结果了。
//遇到叶子结点
if (root.leftnull root.rightnull){//终止处理逻辑
}对于终止逻辑本题使用了List结构 path 来记录路径是因为在下面处理单层递归逻辑的时候要用List方便来做回溯。
终止处理逻辑如下 //遇到叶子结点if (root.leftnull root.rightnull){//输出//StringBuilder用来拼接字符串速度更快StringBuilder sbnew StringBuilder();for (int i0;ipaths.size()-1;i){sb.append(paths.get(i)).append(-);}//记录最后一个节点sb.append(paths.get(paths.size() - 1));//收集一个路径result.add(sb.toString());return;}确定单层递归逻辑
因为是前序遍历需要先处理根节点根节点就是我们要记录路径上的节点先放进path中。
paths.add(root.val);然后是递归和回溯的过程在前面没有判断root是否为空那么在这里递归的时候如果为空就不进行下一层递归了。
所以递归前要加上判断语句下面要递归的节点是否为空如下 if (root.left!null){//左traversal(root.left,paths,result); }if (root.right!null){//右traversal(root.right,paths,result);}此时还没完递归完要做回溯啊因为path 不能一直加入节点它还要删节点然后才能加入新的节点。
那么要怎么回溯呢?我们知道回溯和递归是一一对应的有一个递归就要有一个回溯。所以回溯要和递归永远在一起世界上最遥远的距离是你在花括号里而我在花括号外
哪里有递归哪里就有回溯。
那么代码应该这样写 //递归和回溯是同时进行所以要放在同一个花括号里if (root.left!null){//左traversal(root.left,paths,result);//回溯paths.remove(paths.size()-1);}if (root.right!null){//右traversal(root.right,paths,result);//回溯paths.remove(paths.size()-1);}2.3 java代码实现
class Solution {public ListString binaryTreePaths(TreeNode root) {ListString resnew ArrayList();//存放最终的结果if (rootnull){return res;}ListInteger pathsnew ArrayList();//作为结果中的路径traversal(root,paths,res);return res;}public void traversal(TreeNode root, ListInteger paths,ListString result){//前序遍历 根paths.add(root.val);//遇到叶子结点if (root.leftnull root.rightnull){//输出//StringBuilder用来拼接字符串速度更快StringBuilder sbnew StringBuilder();for (int i0;ipaths.size()-1;i){sb.append(paths.get(i)).append(-);}//记录最后一个节点sb.append(paths.get(paths.size() - 1));//收集一个路径result.add(sb.toString());return;}//递归和回溯是同时进行所以要放在同一个花括号里if (root.left!null){//左traversal(root.left,paths,result);//回溯paths.remove(paths.size()-1);}if (root.right!null){//右traversal(root.right,paths,result);//回溯paths.remove(paths.size()-1);}}
}3.【404】左叶子之和优先掌握递归
【404】左叶子之和
3.1 题目描述
给定二叉树的根节点 root 返回所有左叶子之和。 提示:
节点数在 [1, 1000] 范围内-1000 Node.val 1000
3.2 解题思路
卡哥讲解的很详细可以先看一下视频讲解
二叉树的题目中总有一些规则让你找不到北 | LeetCode404.左叶子之和 划重点啦 此题计算所有左叶子之和而不是二叉树的左侧节点 那么什么是左叶子呢
卡哥给出的左叶子的明确定义节点A的左孩子不为空且左孩子的左右孩子都为空说明是叶子节点那么A节点的左孩子为左叶子节点
可以思考一下下面这三棵二叉树的左叶子之和分别是多少 相信通过这个图大家对最左叶子的定义有明确理解了。
那么我们如何来判断左叶子呢
判断当前节点是不是左叶子是无法判断的必须要通过节点的父节点来判断其左孩子是不是左叶子。
也就是说如果该节点的左节点不为空该节点的左节点的左节点为空该节点的左节点的右节点为空则找到了一个左叶子判断代码如下 /*** 判断左叶子* 1.A节点的左子树不为空* 2.A节点的左子树的左节点为空* 3.A节点的左子树的右节点为空*/if (root.left!null root.left.leftnull root.left.rightnull){//左叶子处理逻辑}递归三部曲 递归的遍历顺序为后序遍历左右根是因为要通过递归函数的返回值来累加求取左叶子数值之和。 确定递归函数的参数和返回值
判断一个树的左叶子节点之和那么一定要传入树的根节点递归函数的返回值为数值之和所以为int 确定终止条件
如果遍历到空节点那么左叶子值一定是0 if (rootnull){return 0;}注意只有当前遍历的节点是父节点才能判断其子节点是不是左叶子。 所以如果当前遍历的节点是叶子节点那其左叶子也必定是0那么终止条件为 if (rootnull){return 0;}//其实这个也可以不写如果不写不影响结果但就会让递归多进行了一层。if (root.leftnull root.rightnull){return 0;}确定单层递归的逻辑
当遇到左叶子节点的时候记录数值然后通过递归求取左子树左叶子之和和 右子树左叶子之和相加便是整个树的左叶子之和。 int leftValuesumOfLeftLeaves(root.left);//左if (root.left!null root.left.leftnull root.left.rightnull){leftValueroot.left.val;}int rightValuesumOfLeftLeaves(root.right);//右int sumleftValuerightValue;//根return sum;3.3 java代码实现
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (rootnull){return 0;}//其实这个也可以不写如果不写不影响结果但就会让递归多进行了一层。if (root.leftnull root.rightnull){return 0;}int leftValuesumOfLeftLeaves(root.left);//左/*** 判断左叶子* 1.A节点的左子树不为空* 2.A节点的左子树的左节点为空* 3.A节点的左子树的右节点为空*/if (root.left!null root.left.leftnull root.left.rightnull){leftValueroot.left.val;}int rightValuesumOfLeftLeaves(root.right);//右int sumleftValuerightValue;//根return sum;}
}
