代码随想录算法训练营第十七天 | 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和

本文主要是介绍代码随想录算法训练营第十七天 | 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[LeetCode] 110. 平衡二叉树

[LeetCode] 110. 平衡二叉树 文章解释

[LeetCode] 110. 平衡二叉树 视频解释

给定一个二叉树,判断它是否是

平衡二叉树

 

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:true

示例 2:

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false

示例 3:

输入:root = []
输出:true

提示:

  • 树中的节点数在范围 [0, 5000]
  • -10^4 <= Node.val <= 10^4

自己看到题目的第一想法 

    1. 什么是平衡二叉树, 平衡二叉树的具体定义是什么呢?

看完代码随想录之后的想法

    1. 平衡二叉树的定义: 每一个节点的左子树和右子树的高度叉不大于一, 则说当前二叉树为平衡二叉树.

    2. 根据定义可以很本能的想到使用递归法来判断是否平衡二叉树. 假设当前节点为 node, 则先计算 node.left 的高度, 再计算 node.right 的高度. 如果 node.left 和 node.right 的差的绝对值大于 1, 则说明当前节点的左右子树破坏了平衡, 因此整颗树都不是平衡二叉树. 此时返回 -1. 如果 node.left 和 node.right 的差的绝对值不大于 1, 则将两者中的大者加一后, 返回给上一层函数.

    3. 一定要记得, 这里是要判断每一个节点是否平衡, 不是只单单判断跟节点的左右节点是否高度上满足平衡条件.

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
// 递归法
class Solution {public boolean isBalanced(TreeNode root) {if (root == null) {return true;}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight != -1 && rightHeight != -1 && Math.abs(leftHeight - rightHeight) <= 1;// 这个条件老是忘记}private int getHeight(TreeNode node) {if (node == null) {return 0;}        if (node.left == null && node.right == null) {return 1;} else {int leftHeight = getHeight(node.left);if (leftHeight == -1) { // 这个条件老是忘记return -1;}int rightHeight = getHeight(node.right);if (rightHeight == -1) { // 这个条件老是忘记return rightHeight;}if (Math.abs(leftHeight - rightHeight) > 1) {return -1;} else {return Math.max(leftHeight, rightHeight) + 1;}}}
}
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
// 迭代法
class Solution {public boolean isBalanced(TreeNode root) {if (root == null) {return true;}Stack<TreeNode> nodes = new Stack<>();TreeNode node = null;nodes.push(root);int leftHeight = 0;int rightHeight = 0;while (!nodes.isEmpty()) {node = nodes.pop();leftHeight = getHeight(node.left);rightHeight = getHeight(node.right);if (Math.abs(leftHeight - rightHeight) > 1) {return false;}if (node.right != null) {nodes.push(node.right);}if (node.left != null) {nodes.push(node.left);}}return true;}private int getHeight(TreeNode node) {if (node == null) {return 0;}Stack<TreeNode> nodes = new Stack<>();int maxDepth = 0;int depth = 0;nodes.push(node);while (!nodes.isEmpty()) {node = nodes.pop();if (node != null) {nodes.push(node);nodes.push(null);depth++;if (node.right != null) {nodes.push(node.right);}if (node.left != null) {nodes.push(node.left);}} else {nodes.pop();depth--;}if (maxDepth < depth) {maxDepth = depth;}}return maxDepth;}
}

自己实现过程中遇到哪些困难

    1. 遇到了一个定义上理解错误的地方. 平衡二叉树的平衡, 说的是每个节点都是平衡的, 而不单单指跟节点的左右子节点是平衡的. 最极端的例子, 一个跟节点, 左节点开始的每个节点只有左节点, 右节点开始的每个节点只有右节点, 假设跟节点的左右子树高度都是3, 这时候当前子树并不是平衡的.

    2. 计算平衡二叉树高度的时候, 老是忘记判断迭代返回高度值为 -1 的情况. 说明对平衡二叉树的判断逻辑还掌握的不够清楚和彻底. 写博客的意义更多的是理清思路, 整理架构. 而现在的模式更像是在记流水账. 需要反思.

[LeetCode] 257. 二叉树的所有路径

[LeetCode] 257. 二叉树的所有路径 文章解释

[LeetCode] 257. 二叉树的所有路径 视频解释

自己看到题目的第一想法

解决的思路:

    1. 首先, 需要遍历整个二叉树.

    2. 当遇到叶子结点的时候, 记录一下当前的路径.

    3. 当遇到叶子结点并且记录过路径后, 需要将叶子结点从路径中删除.

疑惑点:

    如何找到当前叶子结点的上一个节点呢, 只有找到上一个节点, 才能继续遍历.

看完代码随想录之后的想法

    1. 递归法: 递归法的逻辑就是把所有遍历到的元素添加到路径列表里, 同时传给下一个子节点. 这样当到达叶子结点时, 叶子结点就知道从根节点到自己的路径是什么.

    2. 迭代法: 通过迭代法遍历元素,

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/// 递归解法1: 效率一般 49.36%
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();binaryTreePaths(root, new ArrayList<Integer>(), result);return result;}private void binaryTreePaths(TreeNode node, List<Integer> paths, List<String> result) {if (node == null) {return;}paths.add(node.val);StringBuilder strBuilder = new StringBuilder();if (node.left == null && node.right == null) {for (int i = 0; i < paths.size() - 1; i++) {strBuilder.append(paths.get(i) + "->");}strBuilder.append(paths.get(paths.size() - 1));result.add(strBuilder.toString());paths.remove(paths.size() - 1);return;}if (node.left != null) {binaryTreePaths(node.left, paths, result);}if (node.right != null) {binaryTreePaths(node.right, paths, result);}paths.remove(paths.size() - 1);}
}
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/// 递归解法 1 的 StringBuilder 优化版: 
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();binaryTreePaths(root, "", result);return result;}private void binaryTreePaths(TreeNode node, String path, List<String> result) {if (node == null) {return;}StringBuilder strBuilder = new StringBuilder(path);strBuilder.append(node.val);if (node.left == null && node.right == null) {result.add(strBuilder.toString());return;}strBuilder.append("->");if (node.left != null) {binaryTreePaths(node.left, strBuilder.toString(), result);}if (node.right != null) {binaryTreePaths(node.right, strBuilder.toString(), result);}}
}
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/// 迭代法: 49.36%
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();if (root == null) {return result;}Stack<TreeNode> nodes = new Stack<>();List<Integer> paths = new ArrayList<>();TreeNode node = null;nodes.push(root);while (!nodes.isEmpty()) {node = nodes.pop();if (node != null) {if (node.left == null && node.right == null) {StringBuilder strBuilder = new StringBuilder();for (int i = 0; i < paths.size(); i++) {strBuilder.append(paths.get(i)).append("->");}strBuilder.append(node.val);result.add(strBuilder.toString());}nodes.push(node);nodes.push(null);paths.add(node.val);if (node.right != null) {nodes.push(node.right);}if (node.left != null) {nodes.push(node.left);}} else {nodes.pop();paths.remove(paths.size() - 1);}}return result;}
}

[LeetCode] 404. 左叶子之和

[LeetCode] 404. 左叶子之和 文章解释

[LeetCode] 404. 左叶子之和 视频解释

自己看到题目的第一想法

    先看了视频, 所以好像没有什么自己的思考.

    1. 遍历二叉树, 遇到叶子结点的时候, 判断一下当前节点是不是左节点, 是的话将值加入到统计中.

    2. 遍历二叉树的时候不知道当前节点是否是父节点的左节点, 可以采用递归的方式, 将当前节点的父节点传递下来, 或者用一个变量标记当前节点是否是左节点.

    3. 好像整体也没有很难.

看完代码随想录之后的想法

    1. 最核心的部分就是, 如果不使用额外信息的时候. 我们在递归三部曲的循环结束条件中, 需要添加对左侧叶子结点的判断.  即  node.left != null && node.left.left != null && node.left.right != null.

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
// 递归解法
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null) {return 0;}int leftTreeSum = 0;int rightTreeSum = 0;if (root.left != null && root.left.left == null && root.left.right == null) {leftTreeSum = root.left.val;} else {leftTreeSum = sumOfLeftLeaves(root.left);}rightTreeSum = sumOfLeftLeaves(root.right);return leftTreeSum + rightTreeSum;}
}
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
// 迭代解法
class Solution {public int sumOfLeftLeaves(TreeNode root) {if (root == null) {return 0;}Stack<TreeNode> nodes = new Stack<>();TreeNode node = null;nodes.push(root);int sum = 0;while (!nodes.isEmpty()) {node = nodes.pop();if (node.right != null) {nodes.push(node.right);}if (node.left != null && node.left.left == null&& node.left.right == null) {sum += node.left.val;} else if (node.left != null) {nodes.push(node.left);}}return sum;}
}

自己实现过程中遇到哪些困难

    使用迭代实现的时候, 很难想到什么时候要用标记法, 什么时候不需要.

    虽然递归的单次循环条件也时常想不明白, 但是整体来说, 递归方案会更容易调试出来.

    要怎么梳理, 才能让自己掌握得更好呢?

这篇关于代码随想录算法训练营第十七天 | 110. 平衡二叉树、257. 二叉树的所有路径、404. 左叶子之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/999393

相关文章

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1,PDF转Word2,PDF转Excel三、前端页面效果展示总结一

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

通过C#获取PDF中指定文本或所有文本的字体信息

《通过C#获取PDF中指定文本或所有文本的字体信息》在设计和出版行业中,字体的选择和使用对最终作品的质量有着重要影响,然而,有时我们可能会遇到包含未知字体的PDF文件,这使得我们无法准确地复制或修改文... 目录引言C# 获取PDF中指定文本的字体信息C# 获取PDF文档中用到的所有字体信息引言在设计和出

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

python多进程实现数据共享的示例代码

《python多进程实现数据共享的示例代码》本文介绍了Python中多进程实现数据共享的方法,包括使用multiprocessing模块和manager模块这两种方法,具有一定的参考价值,感兴趣的可以... 目录背景进程、进程创建进程间通信 进程间共享数据共享list实践背景 安卓ui自动化框架,使用的是

SpringBoot生成和操作PDF的代码详解

《SpringBoot生成和操作PDF的代码详解》本文主要介绍了在SpringBoot项目下,通过代码和操作步骤,详细的介绍了如何操作PDF,希望可以帮助到准备通过JAVA操作PDF的你,项目框架用的... 目录本文简介PDF文件简介代码实现PDF操作基于PDF模板生成,并下载完全基于代码生成,并保存合并P

SpringBoot基于MyBatis-Plus实现Lambda Query查询的示例代码

《SpringBoot基于MyBatis-Plus实现LambdaQuery查询的示例代码》MyBatis-Plus是MyBatis的增强工具,简化了数据库操作,并提高了开发效率,它提供了多种查询方... 目录引言基础环境配置依赖配置(Maven)application.yml 配置表结构设计demo_st

SpringCloud集成AlloyDB的示例代码

《SpringCloud集成AlloyDB的示例代码》AlloyDB是GoogleCloud提供的一种高度可扩展、强性能的关系型数据库服务,它兼容PostgreSQL,并提供了更快的查询性能... 目录1.AlloyDBjavascript是什么?AlloyDB 的工作原理2.搭建测试环境3.代码工程1.