目錄
- 前言
- 0. *經驗總結
- 0.1 程式員面試金典 P85
- 0.2 各種樹的特點
- 1. 二叉搜尋樹（二叉排序樹）
- 2. 平衡二叉樹
- 3. 完整二叉樹
- 4. 滿二叉樹
- 5. 完滿二叉樹
- 6. 二叉堆（小頂堆和大頂堆）
- 7. 單次查找樹（前序樹）
- 8. 順序存儲二叉樹
- 9. 線索化二叉樹
- 10. 霍夫曼樹
- 11. B樹、B+樹和B*樹
- 0.3 樹的三種周遊方式
- 0.4 圖的表示形式與搜尋
- 1. 節點間通路 [medium]
- 1.1 考慮點
- 1.2 解法
- 1.2.1 廣度優先周遊法（優）
- 1.2.2 深度優先周遊法
- 1.2.3 鄰接矩陣的幂的性質
- 1.2.4 當重複邊為雙向邊時
- 2. 最小高度樹 [easy]
- 2.1 考慮點
- 2.2 解法
- 2.2.1 遞歸法（優）
- 2.2.2 BFS廣度優先周遊
- 3. 特定深度節點連結清單 [medium]
- 3.1 考慮點
- 3.2 解法
- 3.2.1 使用棧暴力法
- 3.2.2 使用棧暴力法（代碼優化縮短）
- 3.2.3 遞歸法（優）
- 4. 檢查平衡性 [easy]
- 4.1 考慮點
- 4.2 解法
- 4.2.1 自頂向下的遞歸
- 4.2.2 自頂向下的遞歸
- 4.2.3 自底向上的遞歸（優）
- 5. 合法二叉搜尋樹 [medium]
- 5.1 考慮點
- 5.2 解法
- 5.2.1 遞歸法
- 5.2.2 中序周遊非遞歸
- 5.2.3 中序周遊遞歸（優）
- 6. 後繼者 [medium]
- 6.1 考慮點
- 6.2 解法
- 6.2.1 中序周遊遞歸法
- 6.2.2 中序周遊非遞歸法（優）
- 8. 首個共同祖先 [medium]
- 8.1 考慮點
- 8.2 解法
- 8.2.1 深度優先周遊
- 8.2.2 深度優先周遊的簡便寫法（優）
- 9. 二叉搜尋樹序列 [hard]
- 9.1 考慮點
- 9.2 解法
- 9.2.1 回溯法+廣度優先周遊
- 10. 檢查子樹 [medium]
- 10.1 考慮點
- 10.2 解法
- 10.2.1 遞歸法（優）
- 12. 求和路徑 [medium]
- 12.1 考慮點
- 12.2 解法
- 12.2.1 暴力法（優）
- 12.2.2 回溯法
- 最後
本系列筆記主要記錄筆者刷《程式員面試金典》算法的一些想法與經驗總結，按專題分類，主要由兩部分構成：經驗值點和經典題目。其中重點放在經典題目上；
本章有10題，标号到12，沒有第7和第11題；
- 樹的基本組成機關是節點node，節點可以封裝左右指針、父節點指針等；
- 可以使用一個名為Tree的類來封裝節點，但在面試中不常用；如果使用Tree類能使代碼簡單或完善，可以使用Tree類；
- 注意區分以下概念，以及一些樹的基本特點與周遊特點《詳情見第0.2點 各種樹的特點》：
- 樹與二叉樹；
- 二叉樹和二叉搜尋樹（又稱二叉排序樹）；
- 平衡與不平衡；
- 完整二叉樹；
- 滿二叉樹；
- 完美二叉樹；
- 二叉堆（小頂堆和大頂堆）
- 單次查找樹（前序樹）
- 順序存儲二叉樹；
- 線索化二叉樹；
- 霍夫曼樹；
- B樹、B+樹和B*樹；
- 全部左邊子孫節點 <= n <= 全部右邊子孫節點；
- 碰到二叉樹時，很多面試者會假定面試官問的是二叉搜尋樹，此時要務必問清是否的二叉搜尋樹；
- 它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹；
- 樹是否平衡需要跟面試官确認；
- 思考方向可以有：“平衡”樹實際上多半意味着“不是非常不平衡的樹”。其平衡性足以保證執行insert和find操作可以在O(log n)的時間複雜度内完成，但不一定是嚴格意義上的平衡樹；
- 平衡二叉樹的常用實作方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等；
- 除最後一層，其它層被填滿，并且最後一層節點從左到右填充；
- 中序周遊結果按順序排列；
- 每個節點都有0個或兩個子節點，不存在隻有一個子節點的節點；
- 完滿二叉樹既是完整二叉樹，又是滿二叉樹；
- 正好有2k-1個節點；
- 一個二叉堆是一個完整二叉樹，每個節點值小于其左右子節點；
- 向最小堆插入元素，總是從最底部、最右邊節點開始，通過與其祖先節點交換來向上傳遞較小值；
- 删除最小堆最小元素，将堆中最後一個元素放在頂節點，通過與子節點交換來向下傳遞較大值；
- 上述兩個算法時間複雜度為O(log n)；
- *節點（有時稱空節點）代表一個完整單次；
- 相比散清單可以識别字元串是否是任何有效單次的字首，可以在O(K)的時間複雜度内檢查字元串是否為有效字首；
- 涉及一組有效單詞的問題可以使用單次查找樹進行優化；
- 從資料存儲來看，數組存儲方式和樹的存儲方式可以互相轉換，即數組可以轉換成樹，樹也可以轉換成數組；
- 順序二叉樹通常隻考慮完全二叉樹；
- 第n個元素的左子節點為 2*n+1；
- 第n個元素的右子節點為 2*n+2；
- 第n個元素的父節點為 (n-1)/2；
- n : 表示二叉樹中的第幾個元素(按0開始編号如圖所示)；
- n個結點的二叉連結清單中含有 2n-(n-1)=n+1 個空指針域。利用二叉連結清單中的空指針域，存放指向該結點在某種周遊次序下的前驅和後繼結點的指針（這種附加的指針稱為"線索"）；
- 給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)；
中序周遊：
void inOrderTraversal(TreeNode node){
if(node != null){
inOrderTraversal(node.left);
visit(node);
inOrderTraversal(node.right);
}
}
前序周遊：
void preOrderTraversal(TreeNode node){
if(node != null){
visit(node);
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
後序周遊：
void postOrderTraversal(TreeNode node){
if(node != null){
postOrderTraversal(node.left);
postOrderTraversal(node.right);
visit(node);
}
}
圖的表示方式：
- 鄰接連結清單法；
- 鄰接矩陣法；
- 鄰接矩陣法使用BFS搜尋，效率會比較低，因為需要疊代所有結點以便找到相鄰節點；
圖的搜尋：
- 深度優先搜尋（DFS）;
- 通路圖中所有節點，或者通路最少節點直至找到某節點，DFS一般比較簡單；
- 廣度優先搜尋（BFS）；
- 如果想找到兩個節點的最短路徑（或任意路徑），BFS一般比較适宜；
- BFS是通過隊列實作；
- 雙向搜尋；
- 雙向搜尋用于查找起始節點和目的節點間的最短路徑；
- 本質上是從起始節點和目的節點同時開始的兩個廣度優先搜尋；
- 當兩個搜尋相遇時，即找到一條路徑
深度優先搜尋（DFS）：
- 前序和樹周遊的其他形式都是一種DFS；
void search(Node root){
if(root == null){
return;
}
visit(root);
root.visited = true;
for each(Node n in root.adjacent){
if(n.visited == false){
search(n);
}
}
}
廣度優先搜尋（BFS）：
void search(Node root){
Queue queue = new Queue();
root.marked = true;
queue.enqueue(root); //加入隊尾
while(!queue.isEmpty()){
Node r = queue.dequeue(); //從隊列頭部删除
visit(r);
for each(Node n in r.adjacent){
if(n.mark == false){
n.marked = true;
queue.enqueue(n);
}
}
}
}
- 詢問面試官重複的邊是否是雙向邊，本題中不是。筆者以為是雙向邊，第五種解法給出思路；
- 可以跟面試官讨論廣度優先搜尋和深度優先搜尋的利弊：
- 廣度優先搜尋：适合查找最短路徑；
- 深度優先搜尋：實作比較簡單，遞歸即可；在通路鄰近節點之前，可能會深度周遊其中一個鄰近節點；
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
Queue<Integer> queue = new LinkedList<>();
boolean[] isVisit = new boolean[n];
isVisit[start] = true;
queue.offer(start);
while( !queue.isEmpty() ){
int thisNode = queue.poll();
int toNode;
for(int i = 0; i < graph.length; i++){
if(graph[i][0] == thisNode){
toNode = graph[i][1];
if(toNode == target){
return true;
}
if(!isVisit[toNode]){
isVisit[toNode] = true;
queue.offer(toNode);
}
}
}
}
return false;
}
- 執行時間：91.21%；記憶體消耗：92.42%；
- 适用于n較少的時候，當n過大會逾時；
private boolean[] visited = null;
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
this.visited = new boolean[graph.length];
return helper(graph, start, target);
}
private boolean helper(int[][] graph, int start, int target) {
for (int i = 0; i < graph.length; ++i) {
// 確定目前路徑未被通路（該判斷主要是為了防止圖中自環出現死循環的情況）
if (!visited[i]) {
// 若目前路徑起點與終點相符，則直接傳回結果
if (graph[i][0] == start && graph[i][1] == target) {
return true;
}
// 設定通路标志
visited[i] = true;
// DFS關鍵代碼，思路：同時逐漸壓縮搜尋區間
if (graph[i][1] == target && helper(graph, start, graph[i][0])) {
return true;
}
// 清除通路标志
visited[i] = false;
}
}
return false;
}
- 執行時間：81.17%；記憶體消耗：97.41%；
- 首先設定通路狀态數組
- 使用DFS「深度優先搜尋」進行遞歸搜尋，逐漸壓縮搜尋區間，直至最終找到start與target在同一個路徑内，則說明查找成功；
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
int[][] adjacentMatrix = new int[n][n];
for (int[] edge : graph) {
adjacentMatrix[edge[0]][edge[1]] = 1;
}
for (int i = 1; i <= n; i++) {
int[][] matrix = matrixPow(adjacentMatrix, i);
if (matrix[start][target] != 0) {
return true;
}
}
return false;
}
public int[][] matrixPow(int[][] matrix, int n) {
int size = matrix.length;
int[][] res = new int[size][];
for (int i = 0; i < size; i++) {
res[i] = Arrays.copyOf(matrix[i], size);
}
for (int i = 1; i < n; i++) {
for (int row = 0; row < size; row++) {
int[] tmp = new int[size];
for (int col = 0; col < size; col++) {
for (int j = 0; j < size; j++) {
tmp[col] += res[row][j] * matrix[j][col];
}
}
res[row] = Arrays.copyOf(tmp, size);
}
}
return res;
}
- 在本測試用例中逾時；
- 用到鄰接矩陣的幂的性質；
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
int[] count = new int[n*(n-1)/2];
for(int i = 0; i < graph.length; i++){
int mark = (2*n-1-graph[i][0])*graph[i][0]/2-1+graph[i][1]-graph[i][0];
count[mark]++;
if(count[mark] == 2){
int cache = graph[i][0];
graph[i][0] = graph[i][1];
graph[i][1] = cache;
}
}
Queue<Integer> queue = new LinkedList<>();
boolean[] isVisit = new boolean[n*(n-1)/2];
queue.offer(start);
while( !queue.isEmpty() ){
int thisNode = queue.poll();
int toNode;
for(int i = 0; i < graph.length; i++){
int mark = (2*n-1-graph[i][0])*graph[i][0]/2-1+graph[i][1]-graph[i][0];
if(graph[i][0] == thisNode && !isVisit[mark]){
toNode = graph[i][1];
if(toNode == target){
return true;
}
queue.offer(toNode);
}
}
}
return false;
}
- 相比前面做法增加了個方向倒轉，也就是把重複邊的方向倒轉；
- 要建立最小生成樹，就必須讓左右子樹的節點數量盡可能接近；
public TreeNode sortedArrayToBST(int[] nums) {
if(nums.length == 0){
return null;
}
int l = 0;
int r = nums.length-1;
return recur(l, r, nums);
}
public TreeNode recur(int l, int r, int[] nums){
if(l > r){
return null;
}
int mid = (l+r)/2;
int headVal = nums[mid];
TreeNode head = new TreeNode(headVal);
head.left = recur(l, mid-1, nums);
head.right = recur(mid+1, r, nums);
return head;
}
- 執行時間：100.00%；記憶體消耗：53.37%；
- 時間複雜度：O(n)。數組中的元素都使用1次，時間複雜度為O(n)；
- 空間複雜度：O(log n )。遞歸使用棧輔助空間，空間複雜度O(log n )；
- 注意遞歸結束條件，沒有等于是因為遞歸裡有對mid增減進行操作；
- 注意遞歸的參數
l
r
public TreeNode sortedArrayToBST(int[] num) {
if (num.length == 0)
return null;
Queue<int[]> rangeQueue = new LinkedList<>();
Queue<TreeNode> nodeQueue = new LinkedList<>();
int lo = 0;
int hi = num.length - 1;
int mid = (lo + hi) >> 1;
TreeNode node = new TreeNode(num[mid]);
rangeQueue.add(new int[]{lo, mid - 1});
rangeQueue.add(new int[]{mid + 1, hi});
nodeQueue.add(node);
nodeQueue.add(node);
while (!rangeQueue.isEmpty()) {
int[] range = rangeQueue.poll();
TreeNode currentNode = nodeQueue.poll();
lo = range[0];
hi = range[1];
if (lo > hi) {
continue;
}
mid = (lo + hi) >> 1;
int midValue = num[mid];
TreeNode newNode = new TreeNode(midValue);
if (midValue > currentNode.val)
currentNode.right = newNode;
else
currentNode.left = newNode;
if (lo < hi) {
rangeQueue.add(new int[]{lo, mid - 1});
rangeQueue.add(new int[]{mid + 1, hi});
nodeQueue.add(newNode);
nodeQueue.add(newNode);
}
}
return node;
}
- 執行時間：100.00%；記憶體消耗：5.01%；
- 把數組不停的分為兩部分，儲存在隊列中，然後不停的出隊，建立結點；
- 不需要逐一周遊每一層，可以用任意方式周遊整棵樹，隻需要記住節點位于哪一層即可；
public ListNode[] listOfDepth(TreeNode tree) {
if(tree == null){
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(tree);
int floor = 1; //第x-1層節點個數
List<ListNode> listArr = new ArrayList<>();
//當隊列不為空
while(!queue.isEmpty()){
//按層處理
int count = 0; //count用來儲存第x層節點個數
ListNode head = null;
ListNode cur = null;
for(int i = 0; i < floor; i++){
TreeNode node = queue.poll();
//建立連結清單
if(i == 0){
head = new ListNode(node.val);
cur = head;
} else {
ListNode nodeL = new ListNode(node.val);
cur.next = nodeL;
cur = nodeL;
}
//加入隊列
if( node.left != null){
count++;
queue.offer(node.left);
}
if(node.right != null){
count++;
queue.offer(node.right);
}
}
listArr.add(head);
floor = count; //替換floor
}
ListNode[] list = new ListNode[listArr.size()];
for(int i = 0; i < listArr.size(); i++){
list[i] = listArr.get(i);
}
return list;
}
- 執行時間：89.59%；記憶體消耗：75.08%；
- 需要注意幾個細節：
-
ListNode cur = null
-
floor = count
-
- 由于事先不知道數組個數，先用一個ArrayList裝起來，然後再轉換成數組；
public ListNode[] listOfDepth(TreeNode tree) {
if(tree == null){
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(tree);
List<ListNode> listArr = new ArrayList<>();
//當隊列不為空
while(!queue.isEmpty()){
//按層處理
int size = queue.size();
ListNode head = new ListNode(0);
ListNode cur = head;
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
//建立連結清單
cur.next = new ListNode(node.val);
//加入隊列
if( node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
cur = cur.next;
}
listArr.add(head.next);
}
return listArr.toArray(new ListNode[] {});
}
- 執行時間：89.59%；記憶體消耗：25.97%；
- 思路同上，更多調用java的api簡化代碼；
public ListNode[] listOfDepth(TreeNode tree) {
List<ListNode> list = new ArrayList<>();
dfs(list, tree, 1);
ListNode[] arr = new ListNode[list.size()];
for (int i = 0; i < arr.length; i++) {
arr[i] = list.get(i);
}
return arr;
}
private void dfs(List<ListNode> list, TreeNode node, int deep) {
if (node == null) {
return;
}
if (deep > list.size()) {
list.add(new ListNode(node.val));
} else {
ListNode n = list.get(deep - 1);
while (n.next != null) {
n = n.next;
}
n.next = new ListNode(node.val);
}
dfs(list, node.left, deep + 1);
dfs(list, node.right, deep + 1);
}
- 執行時間：100.00%；記憶體消耗：96.63%；
- 定義樹深度為deep，同一個深度的儲存到同一個ListNode；
- 其實，隻需要一個checkHeight函數即可，它既可以計算高度，也可以平衡檢查。可以使用整數傳回值表示兩者；
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
int deep = 1;
int rootLeftDeep = findDeep(root.left, deep);
int rootRightDeep = findDeep(root.right, deep);
if(rootLeftDeep == -1 || rootRightDeep == -1){
return false;
}
int result = Math.abs(rootLeftDeep - rootRightDeep);
return result<2;
}
public int findDeep(TreeNode node, int deep){
if(node == null){
return deep-1;
}
if(node.left == null && node.right == null){
return deep;
}
deep++;
int leftDeep = findDeep(node.left,deep);
int rightDeep = findDeep(node.right,deep);
int deepDiff = Math.abs(leftDeep-rightDeep);
return deepDiff>1 ? -1 : Math.max(leftDeep,rightDeep);
}
- 執行時間：88.57%；記憶體消耗：20.48%；
- 方法雖然可行，但不高效，Math.abs()方法會被反複調用計算同一個節點的高度；
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
} else {
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
public int height(TreeNode root) {
if (root == null) {
return 0;
} else {
return Math.max(height(root.left), height(root.right)) + 1;
}
}
- 執行時間：88.57%；記憶體消耗：74.16%；
- 時間複雜度：O(n2)，其中 n 是二叉樹中的節點個數。最壞情況下，二叉樹是滿二叉樹，需要周遊二叉樹中的所有節點，時間複雜度是 O(n)。對于節點 p，如果它的高度是 d，則 height(p) 最多會被調用 d 次（即周遊到它的每一個祖先節點時）。對于平均的情況，一棵樹的高度 h 滿足 O(h)=O(logn)，因為 d≤h，是以總時間複雜度為 O(nlogn)。對于最壞的情況，二叉樹形成鍊式結構，高度為 O(n)，此時總時間複雜度為 O(n2)；
- 空間複雜度：O(n)，其中 n 是二叉樹中的節點個數。空間複雜度主要取決于遞歸調用的層數，遞歸調用的層數不會超過 n；
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}
- 執行時間：88.57%；記憶體消耗：96.72%；
- 時間複雜度：O(n)，其中 n 是二叉樹中的節點個數。使用自底向上的遞歸，每個節點的計算高度和判斷是否平衡都隻需要處理一次，最壞情況下需要周遊二叉樹中的所有節點，是以時間複雜度是 O(n)；
- 有兩種思路：
- 一是利用中序周遊；
- 二是建立在 left <current<right 這項特性上；
class Solution {
Stack<Integer> stack = new Stack<>();
boolean isFlag = false;
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
inOrderTraversal(root);
return !isFlag;
}
public void inOrderTraversal(TreeNode node){
if(isFlag){
return;
}
if(node == null){
return;
}
inOrderTraversal(node.left);
if(stack.isEmpty()){
stack.push(node.val);
} else {
if(stack.peek() >= node.val){
isFlag = true;
return;
} else {
stack.push(node.val);
}
}
inOrderTraversal(node.right);
}
}
- 執行時間：32.30%；記憶體消耗：91.41%；
public boolean isValidBST(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<TreeNode>();
double inorder = -Double.MAX_VALUE;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
// 如果中序周遊得到的節點的值小于等于前一個 inorder，說明不是二叉搜尋樹
if (root.val <= inorder) {
return false;
}
inorder = root.val;
root = root.right;
}
return true;
}
- 執行時間：24.37%；記憶體消耗：98.61%；
- 時間複雜度 : O(n)，其中 n 為二叉樹的節點個數。二叉樹的每個節點最多被通路一次，是以時間複雜度為 O(n)；
- 空間複雜度 : O(n)，其中 n 為二叉樹的節點個數。棧最多存儲 n 個節點，是以需要額外的 O(n) 的空間；
//前一個結點，全局的
TreeNode prev;
public boolean isValidBST(TreeNode root) {
if (root == null)
return true;
//通路左子樹
if (!isValidBST(root.left))
return false;
//通路目前節點：如果目前節點小于等于中序周遊的前一個節點直接傳回false。
if (prev != null && prev.val >= root.val)
return false;
prev = root;
//通路右子樹
if (!isValidBST(root.right))
return false;
return true;
}
- 執行時間：100.00%；記憶體消耗：65.74%；
- 中序周遊時，判斷目前節點是否大于中序周遊的前一個節點，也就是判斷是否有序，如果不大于直接傳回 false
- 因為是二叉搜尋樹，可以很友善找到節點，再根據是否有右子樹分類判斷；
class Solution {
Stack<TreeNode> stack = new Stack<>();
TreeNode findNode = null;
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null || p == null){
return null;
}
inOrderTravarsal(root,p);
return findNode!=null ? findNode : null;
}
public void inOrderTravarsal(TreeNode node, TreeNode p){
if(findNode != null){
return;
}
if(node == null){
return;
}
inOrderTravarsal(node.left, p);
if(stack.isEmpty()){
stack.push(node);
} else {
if(p.equals(stack.peek())){
findNode = node;
stack.pop(); //忘記pop
return;
} else {
stack.push(node);
}
}
inOrderTravarsal(node.right, p);
}
}
- 執行時間：72.07%；記憶體消耗：9.51%；
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode pre = null;
while(root.val!=p.val){
//右邊
if(p.val > root.val){
root = root.right;
}
//左邊
else{
pre = root;
root = root.left;
}
}
//假如沒有右子樹
if(root.right==null){
return pre;
} else {
root = root.right;
while(root.left!=null){
root = root.left;
}
return root;
}
}
- 執行時間：100.00%；記憶體消耗：100.00%；
- 找到節點後，如果右子樹存在，那就是右子樹最左邊的節點。如果右子樹不存在，表示已經通路n層子樹，需要回到n的父節點q；如果n在q的左邊，那就是q。反之需要往上通路，直到找到還未完全周遊的節點x；
- 如果是二叉搜尋樹，可以看看兩條路徑在哪開始分叉；
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
} else if(root.equals(p)){
return p;
} else if(root.equals(q)){
return q;
}
TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
if(leftNode == null && rightNode == null){
return null;
}
if(leftNode != null && rightNode == null){
if(leftNode.equals(q)){
return q;
} else if(leftNode.equals(p)){
return p;
} else {
return leftNode;
}
}
if(leftNode == null && rightNode != null){
if(rightNode.equals(q)){
return q;
} else if(rightNode.equals(p)){
return p;
} else {
return rightNode;
}
}
//注意非空校驗
if((leftNode.equals(p) && rightNode.equals(q)) || (leftNode.equals(q) && rightNode.equals(p))){
return root;
}
return null;
}
- 執行時間：52.31%；記憶體消耗：5.19%；
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 到底了還沒找到，傳回 null
if (root == null) {
return null;
}
// 如果找到了 p 或 q，傳回它
if (root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 如果 left 和 right 都記錄了找到的節點，那麼肯定是一個記錄了 p ，另一個記錄了 q
// 它們分别在以 root 為根的左右子樹中，是以 root 就是它們的最近公共祖先
if (left != null && right != null) {
return root;
}
// 由于節點 p,q 一定在二叉樹中，left和right不會同時為null
// 若 left != null && right == null，說明在左子樹中找到 p 或 q，而在右子樹找不到 p 或 q，則剩下一個也在左子樹
// 是以 left 就是最近公共祖先
// 另一種情況同理
return (left != null) ? left : right;
}
- 執行時間：100.00%；記憶體消耗：91.55%；
- 數組的第一個數必須為頂節點；
- 與左右節點的插入順序無關緊要，但子節點的添加一定要在父節點之後；
private List<List<Integer>> ans;
public List<List<Integer>> BSTSequences(TreeNode root) {
ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
// 如果 root==null 傳回 [[]]
if (root == null) {
ans.add(path);
return ans;
}
List<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 開始進行回溯
bfs(queue, path);
return ans;
}
// 回溯法+廣度優先周遊
private void bfs(List<TreeNode> queue, List<Integer> path) {
// queue 為空說明周遊完了，可以傳回了
if (queue.isEmpty()) {
ans.add(new ArrayList<>(path));
return;
}
// 将 queue 拷貝一份，用于稍後回溯
List<TreeNode> copy = new ArrayList<>(queue);
// 對 queue 進行循環，每循環考慮 “是否 「将目前 cur 節點從 queue 中取出并将其左右子
// 節點加入 queue ，然後将 cur.val 加入到 path 末尾」 ” 的情況進行回溯
for (int i = 0; i < queue.size(); i++) {
TreeNode cur = queue.get(i);
path.add(cur.val);
queue.remove(i);
// 将左右子節點加入隊列
if (cur.left != null) queue.add(cur.left);
if (cur.right != null) queue.add(cur.right);
bfs(queue, path);
// 恢複 path 和 queue ，進行回溯
path.remove(path.size() - 1);
queue = new ArrayList<>(copy);
}
}
- 執行時間：90.30%；記憶體消耗：93.98%；
- 對于這種找出所有情況的題目，回溯法是最容易想到的方法之一了，這道題也可以用回溯法，可以發現剛才選元素的過程和層序周遊的過程其實是一緻的：
-
最開始 queue 中隻有 12 ，隻能選12，将 12 出隊并将它的兩個子節點入隊，得到 [12]；
選了12之後 queue 中剩下 5、19 ，就從 5 和 19 中選一個，得到 [12,5],[12,19]；
- 如果選了 5 ，将 5 出隊并将它的兩個子節點入隊，那麼此時 queue 中剩下 19、2、9，得到 [12,5,2],[12,5,9],[12,5,19]；
- 如果選了 19 ，将 19 出隊并将它的子節點入隊，那麼此時 queue 中剩下 5、15，得到 [12,19,5],[12,19,15]；
- 後續同理；
-
- 這裡的“萬”是幹擾的；
boolean isFound =false;
public boolean checkSubTree(TreeNode t1, TreeNode t2) {
if(t1 == null){
return false;
}
if(t1.val == t2.val){
isFound = true;
return true;
} else {
isFound = false;
}
boolean left;
boolean right;
if(isFound){
left = checkSubTree(t1.left, t2.left);
right = checkSubTree(t1.right, t2.right);
return left && right;
} else {
left = checkSubTree(t1.left, t2);
right = checkSubTree(t1.right, t2);
if(left){
return checkSubTree(t1.left, t2);
}
if(right){
return checkSubTree(t1.right, t2);
}
}
return false;
}
- 執行時間：100.00%；記憶體消耗：46.52%；
- 可以使用散清單優化算法，下面解法沒給出；
class Solution {
int res = 0;
public int pathSum(TreeNode root, int sum) {
int dep = depth(root);
int[] paths = new int[dep];
pathSum(root, sum, 0, paths);
return res;
}
public void pathSum(TreeNode root, int sum, int level, int[] paths) {
if (root == null) {
return;
}
paths[level] = root.val;
int t = 0;
for (int i = level; i >= 0; i--) {
t += paths[i];
if (t == sum) {
res += 1;
}
}
pathSum(root.left, sum, level + 1, paths);
pathSum(root.right, sum, level + 1, paths);
}
public int depth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}
- 執行時間：100.00%；記憶體消耗：69.08%；
private int res = 0;
public int pathSum(TreeNode root, int sum) {
if(root == null) return res;
helper(root, sum);
pathSum(root.left, sum);
pathSum(root.right, sum);
return res;
}
private void helper(TreeNode node, int sum){
if(node == null) return;
sum -= node.val;
if(sum == 0)
res ++;
helper(node.left, sum);
helper(node.right, sum);
sum += node.val;
}
- 執行時間：58.34%；記憶體消耗：10.27%；
新人制作，如有錯誤，歡迎指出，感激不盡！
歡迎關注公衆号，會分享一些更日常的東西！
如需轉載，請标注出處！