第一題: 合并二叉樹

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;
    }
}