完全二叉樹 CBT

設二叉樹的深度為 h , 若非最底層的其他各層的節點數都達到最大個數 , 最底層 h 的所有節點都連續集中在左側的二叉樹叫做 完全二叉樹 .

特點

1. 對任意節點 , 其右分支下的葉子節點的最底層為 L , 則其左分支下的葉子節點的最低層一定是 L 或 L + 1 .
2. 完全二叉樹度為 1 的點只有 1 個或 0 個 .
3. 按層序遍歷的順序訪問 , 度為 1 或 0 的節點的后續節點的度均為 0 .

二叉樹的層序遍歷

層序遍歷是一種廣度優先搜索 , 要借助 隊列 數據結構實現 , 核心邏輯如下 :

1. 初始化隊列 , 把根節點加入隊列 .
2. 從隊列取出一個節點 , 將該節點的左右節點加入隊列 , 重復處理至隊列為空 .

class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(int val){this.val = val;}public static List<Integer> levelOrderTraversal(TreeNode root){Queue<TreeNode> queue = new LinkedList<>();List<Integer> list = new ArrayList<>();if (root == null) {return list;}queue.offer(root);while(!queue.isEmpty()){TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}return list;}
}

Queue 的 offer 方法會將 null 加入隊列 , 因此我們要加入條件語句避免產生空指針異常 .

判斷二叉樹是否為完全二叉樹

因為完全二叉樹最底層 h 的所有節點都連續集中在左側 , 且按層序遍歷的順序訪問 , 度為 1 或 0 的節點的后續節點的度均為 0 ( 特點 3 ) , 判斷是否為完全二叉樹較常用的方法要借助 二叉樹的層序遍歷 , 核心邏輯如下 :

1. 對二叉樹進行層序遍歷 , 使用隊列保存節點 .
2. 遍歷過程中維護標識符 end , 其表示是否遇到過度為 1 或 0 的節點 .
3. end 標識符翻轉后如果再次遇到有左右任一子節點的節點 , 直接返回 .

class TreeNode{int val;TreeNode left;TreeNode right;TreeNode(int val){this.val = val;}public static Boolean isCBTorNot(TreeNode root){Queue<TreeNode> queue = new LinkedList<>();if (root == null) {return true;}queue.offer(root);boolean end = false;while(!queue.isEmpty()){TreeNode node = queue.poll();if(node.left != null){if(end) return false;queue.offer(node.left);}else end = true;if(node.right != null){if(end) return false;queue.offer(node.right);}else end = true;}return true;}
}

完全二叉樹的數組表示

為什么可以使用數組表示 ?

完全二叉樹非最底層的其他各層的節點數都達到最大個數 , 最底層 h 的所有節點都連續集中在左側 , 使得使用數組存儲時能夠緊密排列 , 避免空間浪費 .

父子節點的索引關系

推導過程如圖 , 結論 :

• 父節點的數組索引為 n , 則左子節點的數組索引為 2 * n + 1 , 右子節點的數組索引為 2 * n + 2 , 祖父節點的數組索引為 ( n - 1 ) / 2 .
  

堆 Heap

堆是滿足特定條件的完全二叉樹 , 主要分為 大頂堆 和 小頂堆 兩種類型 , 大頂堆指 任意節點值 >= 其子節點值 , 小頂堆指 任意節點值 <= 其子節點值 .

堆化

堆化是將無序數組轉化為堆的過程 . 添加元素入堆時 :

1. 給定元素 val , 我們首先將該元素添加到堆底 .
2. val 可能大于堆中其他元素 , 此時堆被暫時破壞 , 我們要從堆底至頂進行堆化 .
3. 比較 val 節點與其節點的值 , 若插入節點更大則交換二者 , 重復執行操作直到節點上升到根節點或其父節點更大時結束 .

初始化無序數組為堆時 :

1. 對于每個非葉子節點執行下沉操作 : 比較該節點與左右子節點 , 若該節點值小于子節點最大值 , 則交換該節點與最大值子節點 .
2. 重復操作直到節點下沉到葉子節點或該節點值大于或等于左右子節點值的最大值 .

堆的節點總數為 n , 樹的層數為 log n , 堆化操作的迭代次數至多為 log n , 知元素入堆操作的時間復雜度是 O(log n) .

class Heap {public static void heapify(int[] arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest]) largest = left;if (right < n && arr[right] > arr[largest]) largest = right;if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest);}}public static void buildMaxHeap(int[] arr) {int n = arr.length;for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}}

堆排序

堆排序基于頂堆的特性 , 重復將堆頂元素與堆尾元素交換 , 堆化非隊尾元素的剩余元素 直至數組有序 . 堆的節點數為 n , 堆化操作的時間復雜度為 log n , 因此堆排序的時間復雜度是 O(n log n) , 堆排序基于原地交換 , 空間復雜度為常數級 , 是性能良好的排序方法 .

class Heap{public static void heapSort(int[] arr) {int n = arr.length;for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}for (int i = n - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}}
}

優先隊列 PriorityQueue

優先隊列是特殊的隊列數據結構 , 在 Java PriorityQueue 類中 , 默認優先級為從小到大的自然排序 , 可以通過 lambda 表達式自定義比較器 Comparator 函數類型 .

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); // 默認為自然順序
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder()); // 更改比較器為降序

如果要儲存自定義引用數據類型時 , 有兩種方式定義元素優先級 :

1. 引用類實現 Comparable 接口 : 在類中實現 compareTo() 方法 .
2. 在初始化 PriorityQueue 時傳入比較器對象 .

class Person{private String name;private int age;Person(String name, int age){this.name = name;this.age = age;}@Overridepublic int compareTo(Person person){retutn Integer.compare(this.age, person.age);}
}
public class Main{public static void main(String[] args){PriorityQueue<Person> pq = new PriorityQueue<>();// 或PriorityQueue<Person> pq = new PriorityQueue<>((p1, p2) -> Integer.compare(p2.getAge(), p1.getAge()));}
}

Java 優先隊列的方法與隊列類似 .

23. 合并 K 個升序鏈表

class Solution {public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);for (ListNode head : lists) {if (head != null) {pq.offer(head);}}ListNode dummy = new ListNode();ListNode cur = dummy;while (!pq.isEmpty()) {ListNode node = pq.poll();if (node.next != null) {pq.offer(node.next);}cur.next = node;cur = cur.next;}return dummy.next;}
}