宁远做网站msoer,太原做网站个人,sem推广是什么意思,济南定制网站建设公司代码随想录算法训练营第十七天|110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和
110.平衡二叉树
给定一个二叉树#xff0c;判断它是否是
平衡二叉树
示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,15,7]
输出#xff1a;true题解#xff1a;平衡…代码随想录算法训练营第十七天|110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和
110.平衡二叉树
给定一个二叉树判断它是否是
平衡二叉树
示例 1 输入root [3,9,20,null,null,15,7]
输出true题解平衡二叉树是指每个节点的左右子树的高度不能超过1。采用后序遍历的递归方式来解决问题因为当前节点的深度需要下一层节点深度返回加一所以递归选择左右中的遍历方式。
代码
class Solution {public boolean isBalanced(TreeNode root) {return houxv(root)!-1;}//求深度后序遍历public int houxv(TreeNode node){if(nodenull) return 0;int leftLenhouxv(node.left);if(leftLen-1) return -1;int rightLenhouxv(node.right);if(rightLen-1) return -1;if(Math.abs(leftLen-rightLen)1){return -1;}return Math.max(leftLen,rightLen)1;}
}257.二叉树的所有路径
给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1 输入root [1,2,3,null,5]
输出[1-2-5,1-3]题解前序遍历。其中用到了回溯法。将当前节点的val加入list后判断左右孩子的状态然后再递归找另外一条路径需要返回上一个节点val的list列表需要remove。
代码
class Solution {public ListString binaryTreePaths(TreeNode root) {ListString resnew ArrayList();if(rootnull) return res;ListInteger pathnew ArrayList();resqianxv(root,res,path);return res;}public ListString qianxv(TreeNode node,ListString res,ListInteger path){path.add(node.val);//说明一条线路遍历完了if(node.leftnull node.rightnull){StringBuilder sbnew StringBuilder();for(int i0;ipath.size()-1;i){sb.append(path.get(i)-);}sb.append(path.get(path.size()-1));res.add(sb.toString());}if(node.left!null) {qianxv(node.left,res,path);path.remove(path.size()-1);}if(node.right!null) {qianxv(node.right,res,path);path.remove(path.size()-1);}return res;}
}404.左叶子之和
给定二叉树的根节点 root 返回所有左叶子之和。
示例 1 输入: root [3,9,20,null,null,15,7]
输出: 24
解释: 在这个二叉树中有两个左叶子分别是 9 和 15所以返回 24题解这个题可以轻松的判断只不是叶子节点难点在于怎么判断它是不是左节点呢。所以不判断到叶子结点而是判断到叶子结点的父节点然后再判断该节点的左节点的左右孩子是不是都为空。采用后序遍历的方式从底部开始收集数据然后返回给上一层。
代码
class Solution {public int sumOfLeftLeaves(TreeNode root) {if(rootnull) return 0;if(root.leftnull root.rightnull) return 0;//后序遍历 左右中int llensumOfLeftLeaves(root.left);int rlensumOfLeftLeaves(root.right);if(root.left!null root.left.leftnull root.left.rightnull){llenroot.left.val;}//中int sumllenrlen;return sum;}
}
