257. 二叉樹的所有路徑

題目：

給你一個二叉樹的根節點 root ，按任意順序 ，回傳所有從根節點到葉子節點的路徑，

題解：

constructPaths函式：

1.引數：當前節點，當前路徑，以及最侄訓傳的list集合paths

2.如果當前節點不為空，則將該節點添加到path中；

3.在不為空的基礎上，判斷當前節點是否為葉子節點，如果為葉子節點則代表這條path結束，將path添加至paths中；如果不是葉子節點，則繼續遍歷它的左右子樹，

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        constructPaths(root,"",res);
        return res;
    }
    public void constructPaths(TreeNode root, String path, List<String> paths){
        if (root!=null){
            StringBuffer sb = new StringBuffer(path);
            sb.append(Integer.toString(root.val));
            if (root.left==null&&root.right==null){//為葉子節點
                paths.add(sb.toString());
            }else {
                sb.append("->");
                constructPaths(root.left,sb.toString(),paths);
                constructPaths(root.right,sb.toString(),paths);
            }
        }
    }

劍指 Offer 34. 二叉樹中和為某一值的路徑

題目：

給你二叉樹的根節點root 和一個整數目標和 targetSum ，找出所有 從根節點到葉子節點 路徑總和等于給定目標和的路徑，

題解：

和上一題的思路一致，

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        constructPaths(root,0,target,path,res);
        return res;
    }
    public void constructPaths(TreeNode root, int sum,int target,List<Integer> path,List<List<Integer>> paths){

        if (root!=null){
            sum = sum + root.val;
            List<Integer> list = new ArrayList<>(path);//用來獲取截止到目前為止路徑中的節點
            list.add(root.val);
            if (root.right==null&&root.left==null){
                if (sum==target){
                    paths.add(list);
                }
            }else {
                constructPaths(root.left,sum,target,list,paths);
                constructPaths(root.right,sum,target,list,paths);
            }
        }
    }

劍指 Offer 36. 二叉搜索樹與雙向鏈表

題目：

輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的回圈雙向鏈表，要求不能創建任何新的節點，只能調整樹中節點指標的指向，

題解：

1.對線索二叉樹進行中序遍歷，遍歷結果為遞增的，將結果存盤在list集合中；

2.在主函式中，對list集合進行遍歷，首先構成雙向鏈表；

3.將雙向鏈表的首尾連接形成雙向回圈鏈表，

 public Node treeToDoublyList(Node root) {
        
        if (root==null){
            return null;
        }
        List<Integer> list = new ArrayList<>();
        inOrderRecur(root,list);
        Node head = new Node(list.get(0));
        Node temp = head;
        for (int i=1;i<list.size();i++){
            Node node = new Node(list.get(i));
            temp.right=node;
            node.left=temp;
            temp=temp.right;
        }
        temp.right=head;
        head.left=temp;
        return head;
    }
    public void inOrderRecur(Node root , List<Integer> list) {
        if (root == null) {
            return;
        }
        inOrderRecur(root.left,list);
        list.add(root.val);
        inOrderRecur(root.right,list);
    }

劍指 Offer 54. 二叉搜索樹的第k大節點

題目：

給定一棵二叉搜索樹，請找出其中第k大的節點，

題解1：

按照上一題的思路，對線索二叉樹進行中序遍歷，將遍歷結果存盤在list集合中，回傳list集合中第k大的值即可，

 public int kthLargest(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inOrderRecur(root,list);
        return list.get(list.size()-k);
    }
    public void inOrderRecur(TreeNode root , List<Integer> list) {
        if (root == null) {
            return;
        }
        inOrderRecur(root.left,list);
        list.add(root.val);
        inOrderRecur(root.right,list);
    }

題解2：

1.對線索二叉樹進行遍歷，遍歷的順序為先遍歷右子樹，再遍歷根節點，再遍歷左子樹，遍歷結果為遞減序列；

2.使用全域變數sum來記錄當前遞回節點的個數，當sum==k時，表明此時根節點為第k大的值，結束遞回回傳值即可，

class Solution {
    int k,res,sum=0;
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        postOrderRecur(root);
        return res;
    }

    public void postOrderRecur(TreeNode root) {
       
        if (root == null) {
            return ;
        }
        postOrderRecur(root.right);
        sum++;//記錄此時訪問節點的數量
        if (sum == k){
            res = root.val;
            return;
        }
        postOrderRecur(root.left);
    }
}

劍指 Offer 45. 把陣列排成最小的數

題目：

輸入一個非負整數陣列，把陣列里所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個，

題解：

把陣列排成最小的數

兩個字串a和b，如果a+b>b+a，則a應該在b的后面

Arrays.sort()：[sort](…/…/java/util/Arrays.html#sort(T[], java.util.Comparator))(T[] a, Comparator<? super T> c)可以自定義一個比較器

    public String minNumber(int[] nums) {

        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }

劍指 Offer 61. 撲克牌中的順子

題目：

從若干副撲克牌中隨機抽 5 張牌，判斷是不是一個順子，即這5張牌是不是連續的，2～10為數字本身，A為1，J為11，Q為12，K為13，而大、小王為 0 ，可以看成任意數字，A 不能視為 14，

題解：

集合 Set / 排序，清晰圖解

能夠連成順子的兩個條件：

• 陣列中無重復數字
• 最大值和最小值的差值最大為4

    public boolean isStraight(int[] nums) {
        
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        Set<Integer> set = new HashSet<>();//確保沒有重復的
        for (int num:nums){
            if(num == 0) continue; // 跳過大小王
            min = Math.min(min,num);
            max = Math.max(max,num);
            if (set.contains(num)){
                return false;
            }
            set.add(num);
        }
        return max-min<5;
    }

劍指 Offer 40. 最小的k個數

題目：

輸入整數陣列 arr ，找出其中最小的 k 個數，例如，輸入4、5、1、6、2、7、3、8這8個數字，則最小的4個數字是1、2、3、4，

題解：

直接sort

  public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        Arrays.sort(arr);
        for (int i=0;i<k;i++){
            res[i]=arr[i];
        }
        return res;
    }

劍指 Offer 41. 資料流中的中位數

題目：

如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值，如果從資料流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值，

題解：

優先佇列 / 堆，清晰圖解

1.建立大頂堆和小頂堆：PriorityQueue<>()默認建立小頂堆，PriorityQueue<>((x, y) -> (y - x))建立大頂堆；

2.如果此時A和B兩個堆的數量不相等，向B中add，反之向A中add；

3.在向B中add時，有可能此時的num并不屬于較小的那一部分，因此需要先向A中add，然后將A的堆頂元素add至B中，

class MedianFinder {
    Queue<Integer> A, B;
    
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小頂堆，保存較大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 實作大頂堆，保存較小的一半
    }
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

emo了好久，我終于和自己和解了！