LeetCode Day17 110和amp;257和amp;404
110. 平衡二叉树这题只要求出左右子树的高度然后求绝对差即可,需要特别注意左右子树为空的情况。
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1;
}
public int getHeight(TreeNode root){
if(root == null) return 0;
int left = getHeight(root.left);
int right = getHeight(root.right);
if(left == -1) return -1;
if(right == -1) return -1;
if(Math.abs(left - right) > 1){
return -1;
}
return Math.max(left, right) 1;
}
}
257. 二叉树的所有路径 题目要求从根节点到叶子的路径,所以需要前序遍历,这样才方便让父节点指向孩子节点,找到对应的路径。同时需要考虑回溯,因为我们要把路径记录下来,需要回溯来回退一个路径再进入另一个路径。
lass Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if(root == null){
return res;
}
List<Integer> paths = new ArrayList<>();
traversal(root, paths, res);
return res;
}
private void traversal(TreeNode root, List<Integer> paths, List<String> res){
paths.add(root.val);
if(root.left == null && root.right == null){
StringBuilder sb = new StringBuilder();
for(int i = 0; i < paths.size() - 1; i ){
sb.append(paths.get(i)).append("->");
}
sb.append(paths.get(paths.size() - 1));
res.add(sb.toString());
return;
}
if(root.left != null){
traversal(root.left, paths, res);
paths.remove(paths.size() - 1);
}
if(root.right != null){
traversal(root.right, paths, res);
paths.remove(paths.size() - 1);
}
}
}
404. 左叶子之和 首先需要给出左叶子的明确定义:节点A的左孩子不为空,且左孩子的左右孩子都为空(说明是叶子节点),那么A节点的左孩子为左叶子节点。 那么我们找到左叶子结点的方法只能是通过该叶子结点的父节点来找。如果该节点的左节点不为空,该节点的左节点的左节点为空,该节点的左节点的右节点为空,则找到了一个左叶子。 最后左叶子的和就是左子树的左叶子结点 右子树的左叶子结点
class Solution {
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;
}
return midValue leftValue rightValue;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgiibia
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13