代码随想录第十五天| 110.平衡二叉树 、 257. 二叉树的所有路径 、404.左叶子之和、222.完全二叉树的节点个数
110. 平衡二叉树
题目描述
给定一个二叉树，判断它是否是平衡二叉树。平衡二叉树的定义是：对于每个节点，其左右子树的高度差不超过1。
解题思路
- 递归求高度：设计一个递归函数
getHeight，用于计算每个节点的高度，同时在递归过程中判断该节点的左右子树是否平衡。 - 平衡性判断：在
getHeight函数中，如果当前节点的左右子树高度差超过1，则直接返回-1，表示该子树不平衡。 - 终止条件：当某个子树不平衡时，递归会一路返回
-1，最终使isBalanced方法返回false。 - 递归返回高度：如果左右子树平衡，则
getHeight返回节点的高度（即1 + Math.max(leftHeight, rightHeight)），用于上层判断。
代码实现
class Solution {
public int getHeight(TreeNode node){
if(node==null){
return 0;
}
int leftHeight = getHeight(node.left);
if(leftHeight==-1){
return -1;
}
int rightHeight = getHeight(node.right);
if(rightHeight==-1){
return -1;
}
int result;
if(Math.abs(rightHeight-leftHeight)>1){
return -1;
}else {
result = 1+Math.max(rightHeight,leftHeight);
}
return result;
}
public boolean isBalanced(TreeNode root) {
int result = getHeight(root);
if(result==-1){
return false;
}else {
return true;
}
}
}
257. 二叉树的所有路径
题目描述
给定一个二叉树，返回所有从根节点到叶子节点的路径。
解题思路
- 深度优先遍历：使用深度优先遍历（DFS）方法遍历二叉树，记录每条从根到叶子的路径。
- 路径存储：定义一个列表
paths用于存储当前路径中的节点值，当遍历到叶子节点时，将路径拼接成字符串并加入结果列表res中。 - 回溯：每次递归返回上层节点时，从
paths中移除最后一个节点值，以回溯至之前的状态，继续生成其他路径。
代码实现
class 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;
}
public 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. 左叶子之和
题目描述
计算给定二叉树的所有左叶子节点的和。左叶子节点是指在父节点的左子树中且没有子节点的节点。
解题思路
- 递归遍历：使用递归方式遍历每个节点，分别计算左子树和右子树中左叶子节点的和。
- 判断左叶子节点：在递归过程中，如果一个节点的左子节点存在且是叶子节点（即没有左右子节点），则将其值加入左叶子和中。
- 递归返回和：每个节点返回的结果是该节点下所有左叶子节点的和，递归最终得到整棵树的左叶子和。
代码实现
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null && root.right==null){
return 0;
}
int leftvalue = sumOfLeftLeaves(root.left);
if(root.left != null && root.left.left == null && root.left.right == null){
leftvalue = root.left.val;
}
int rightvalue = sumOfLeftLeaves(root.right);
return leftvalue+rightvalue;
}
}
222. 完全二叉树的节点个数
题目描述
给定一个完全二叉树，求出该树的节点总数。
解题思路
-
递归计数法：
- 使用简单的递归方法，分别统计左子树和右子树的节点数，加上根节点，即可得到总节点数。
- 时间复杂度为 O(n)，其中 n 是节点总数。
-
利用完全二叉树特性优化：
- 计算完全二叉树的左深度
leftDepth和右深度rightDepth。 - 如果左右深度相等，则整棵树是满二叉树，其节点数为 ( 2^{\text{leftDepth} + 1} - 1 )。
- 如果左右深度不相等，递归计算左子树和右子树的节点数之和。
- 这种方法利用了完全二叉树的结构特性，降低了时间复杂度。
- 计算完全二叉树的左深度
代码实现
class Solution {
public int countNodes(TreeNode root) {
if(root==null){
return 0;
}
int leftnode =countNodes(root.left);
int rightnode =countNodes(root.right);
return leftnode+rightnode+1;
}
}
class Solution {
public int countNodes(TreeNode root) {
if(root==null){
return 0;
}
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth =0,rightDepth =0;
while(left!=null){
left = left.left;
leftDepth++;
}
while(right!=null){
right = right.right;
rightDepth++;
}
if(leftDepth==rightDepth){
return (2 << leftDepth)-1;
}
int leftnode = countNodes(root.left);
int rightnode = countNodes(root.right);
return leftnode+rightnode+1;
}
}