代码随想录算法训练营第15天：Leetcode110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之和 , 222.完全二叉树的节点个数

前言

zaccheo打卡代码随想录第15天

---

Leetcode110.平衡二叉树

题目链接：110. 平衡二叉树 - 力扣（LeetCode）

文章链接：代码随想录

        在做这道题之前要先搞清楚什么是平衡二叉树，平衡二叉树的定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。其次递归看着很简单但是做出来之后却很难理解不明白是怎么做出来的，下面贴张图理解一下递归遍历二叉树：

这道题也是通过递归，遍历到每个节点的左右节点，然后判断左右节点的高度差是否大于1即可，具体代码如下：

class Solution {
    public boolean isBalanced(TreeNode root) {
        return banlance(root)!=-1;
    }

public int banlance(TreeNode root){
if(root==null){
return 0;
}
int lengthleft=banlance(root.left);
if(lengthleft==-1){
return -1;
}
int lengthright=banlance(root.right);
if(lengthright==-1){
return -1;
}

if(Math.abs(lengthleft-lengthright)>1){
return -1;
}

return Math.max(lengthleft,lengthright)+1;
}
}

---

Leetcode222.完全二叉树的节点个数

题目链接：222. 完全二叉树的节点个数 - 力扣（LeetCode）

文章链接：代码随想录

        这道题我的思路很简单，首先创建一个集合，然后对二叉树进行递归遍历，遍历到的元素存入集合中，最后返回集合的size即可，具体代码如下：

class Solution {
    public int countNodes(TreeNode root) {
        List<Integer> ls=new ArrayList<>();
purber(root,ls);
return ls.size();
    }

public void purber(TreeNode root,List<Integer> ls){
if(root==null){
return;
}
       ls.add(root.val);
   purber(root.left,ls);
   purber(root.right,ls);

}
}

---

Leetcode404.左叶子之和

题目链接：404. 左叶子之和 - 力扣（LeetCode）

文章链接：代码随想录

不出所料，这道题还是需要用到递归（感觉进了二叉树这片林子递归就没断过。。。)，首先要设置左叶子节点的条件，如果一个节点node的子节点是左叶子节点那必须满足条件

node.left!=null&&node.left.left==null7&node.left.right==null

满足这个条件的子节点即为左叶子节点就可以参与到运算中，具体实现代码如下：

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root==null){
return 0;
}
int left=sumOfLeftLeaves(root.left);
int right=sumOfLeftLeaves(root.right);
int mid=0;
if(root.left!=null&&root.left.left==null&&root.left.right==null){
mid=root.left.val;
}
int sum=mid+right+left;

return sum;
    }
}

---

Leetcode257. 二叉树的所有路径

题目链接：. - 力扣（LeetCode）

文章链接：代码随想录

        这道题是我对着卡哥的代码看了很长时间才理出来思路，刚拿到手也是一点思路没有，这道题的解题过程使用了递归和回溯，大致思路就是想递归遍历二叉树的一条边，遍历完成之后将这条边处理好存入集合中，接着再原来遍历到的那条边的末端回退一个节点，再遍历那个节点的右子节点最后得出另一条路径以此类推最后得出二叉树的所有路径，看完之后直呼巧妙，现在还没有完全理解，先明白思路，之后刷再详细了解吧，完成代码如下：

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<Integer> ls=new ArrayList<>();
List<String> list=new ArrayList<>();
if(root==null){
return null;
}
method(root,ls,list);
return list;
    }

public void method(TreeNode root,List<Integer> ls,List<String> list){
ls.add(root.val);
if(root.left==null&&root.right==null){
StringBuffer sb=new StringBuffer();
for(int i=0;i<ls.size()-1;i++){
sb.append(ls.get(i)).append("->");
}

sb.append(ls.get(ls.size()-1));
list.add(sb.toString());
return;
}
if(root.left!=null){
method(root.left,ls,list);
ls.remove(ls.size()-1);
}
if(root.right!=null){
method(root.right,ls,list);
ls.remove(ls.size()-1);
}
}
}

原文地址：https://blog.csdn.net/AKA_ZHANG/article/details/143768515

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！