LeetCode 二叉树相关Easy题 --- 二叉树

文章目录

第一题: 合并二叉树

LeetCode 617 : 合并二叉树
描述:
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

解题思路:

1. 用前序遍历的方法递归两棵树
2. 每次递归 判断是否为空 ① root1 为空 ,返回 root2 即可 ② root2 为空 ,返回 root1 即可
3. 定义一个新的树 merge ,递归时,将2颗树的节点的值加起来放入merge.val中
4. 递归合并左右子树;
5. 最后返回merge即可.

画图解析:

代码实现:

classSolution{publicTreeNodemergeTrees(TreeNode root1,TreeNode root2){if(root1 ==null){return root2;//root1为空,返回root2}if(root2 ==null){return root1;//root2为空,返回root1}//创建一个新的节点TreeNode merge =newTreeNode(root1.val + root2.val);//该节点的左子树
        merge.left =mergeTrees(root1.left,root2.left);//该节点的右子树
        merge.right =mergeTrees(root1.right,root2.right);return merge;//返回该节点}}

第二题: 二叉树的层平均值

LeetCode 637 : 二叉树的层平均值
描述:
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

解题思路:

1. 使用层序遍历的方法,将每一层的值加到一起
2. 记录每一层的数据的个数
3. 用每层的total ÷ 每层的个数 就是 每层的平均值
4. 注意 这里的节点的范围,每层的总和可能超出int,所以这里要用long

画图解析:

代码实现:

classSolution{publicList<Double>averageOfLevels(TreeNode root){List<Double> list =newArrayList<>();if(root ==null)return list;//为空直接返回Queue<TreeNode> queue =newLinkedList<>();
        queue.offer(root);while(!queue.isEmpty()){long sum =0;//sum用来表示每层的总和int size = queue.size();int count = size;//count用来表示每层元素的个数while(size !=0){//size为空的时候表示这一层已经记录完TreeNode top =queue.poll();
                sum += top.val;//每次出队的时候,将数据加到sum中if(top.left !=null){
                    queue.offer(top.left);}if(top.right !=null){
                    queue.offer(top.right);}
                size--;}//走出循环表示每层结束,所以将求得的平均值放入list中
            list.add(sum /(count*1.0));}return list;}}

第三题: 二叉树中第二小的节点

LeetCode 671 : 二叉树中第二小的节点
描述:
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。
更正式地说，

root.val = min(root.left.val, root.right.val)

总成立。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

解题思路:

1. 题目可以知道,根节点一定是最小值
2. 所以使用前序遍历的方法,分别递归左子树 和右子树
3. 递归只要找到比根节点大的值就直接返回,节点为空时(没有找到),返回-1;
4. 如果左右子树都有比根节点大的值,就返回小的那个值
5. 如果左边没有就返回右边
6. 如果右边没有就返回左边
7. 如果两边都没有就返回-1;

画图解析:

代码实现:

classSolution{publicintfindSecondMinimumValue(TreeNode root){returngetMinValue(root,root.val);}publicintgetMinValue(TreeNode root,int val){if(root==null)return-1;// 没有找到比根节点大的返回-1;if(root.val > val)return root.val;//找到比根节点大的就返回int left =getMinValue(root.left,val);//left为左子树所求的值int right =getMinValue(root.right,val);//right为右子树所求的值// 如果都有比根节点大的值,返回较小的那个if(left >=0&& right >=0){returnMath.min(left,right);}// 如果 左有 右没有  返回左// 如果 左没有 右有  返回右// 如果 左没有 右没有 返回任意一个// 三种情况综合 就是返回最大的那个returnMath.max(left,right);}}

第四题: 叶子相似的树

LeetCode 872 : 叶子相似的树
描述:
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

解题思路:

1. 使用前序遍历的方法,每次递归,当root的左子树和右子树都为空的时候,存入list中
2. 递归结束,list中就是该树的叶子节点
3. 将两棵树的list进行比较相同就是true

代码实现:

classSolution{publicbooleanleafSimilar(TreeNode root1,TreeNode root2){// 如果两个树的list不相同则为false,否则就是true;returngetNode(root1).equals(getNode(root2));}publicList<Integer>getNode(TreeNode root){List<Integer> list =newArrayList<>();if(root ==null){return list;}// 左右子树都不存在 就是叶子节点if(root.left ==null&& root.right ==null){
            list.add(root.val);}
        list.addAll(getNode(root.left));
        list.addAll(getNode(root.right));return list;}}