第一题: 合并二叉树

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

解题思路:

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

画图解析:

代码实现:

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null){
            return root2;//root1为空,返回root2
        }
        if(root2 == null){
            return root1;//root2为空,返回root1
        }
        //创建一个新的节点
        TreeNode merge = new TreeNode(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

画图解析:

代码实现:

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();
        if(root == null) return list;//为空直接返回
        Queue<TreeNode> queue = new LinkedList<>();
        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;

画图解析:

代码实现:

class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        return getMinValue(root,root.val);
    }
    public int getMinValue(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){
            return Math.min(left,right);
        }
        // 如果 左有 右没有  返回左
        // 如果 左没有 右有  返回右
        // 如果 左没有 右没有 返回任意一个
        // 三种情况综合 就是返回最大的那个
        return Math.max(left,right);
    }
}

第四题: 叶子相似的树

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

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

解题思路:

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

代码实现:

class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        // 如果两个树的list不相同则为false,否则就是true;
        return getNode(root1).equals(getNode(root2));
    }

    public List<Integer> getNode(TreeNode root){
        List<Integer> list = new ArrayList<>();
        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;
    }
}