樹(shù)狀結(jié)構(gòu)的算法題時(shí)間復(fù)雜度是相對(duì)比較難的

因?yàn)橛袃煞N情況，一種是普通遍歷，另一種是分治算法

?

---

?

而如Leetcode109.?Convert Sorted List to Binary Search Tree

這題的代碼如下

class Solution {public TreeNode sortedListToBST(ListNode head) {if (head == null) return null;if (head.next == null) return new TreeNode(head.val);ListNode preMid = findPreMid(head);ListNode mid = preMid.next;preMid.next = null;TreeNode node = new TreeNode(mid.val);node.left = sortedListToBST(head);node.right = sortedListToBST(mid.next);return node;}public ListNode findPreMid(ListNode head) {ListNode slow = head, fast = head.next, preMid = slow;while (fast != null && fast.next != null) {preMid = slow;slow = slow.next;fast = fast.next.next;}return preMid;} }

很明顯就是一個(gè)創(chuàng)建BST的題，由于題目明確說(shuō)明是BST，所以這題可以看作一個(gè)類似快速排序的分治算法

這里牽扯到遞歸處理分治算法的概念，遞歸算法的時(shí)間復(fù)雜度計(jì)算需要畫圖闡述

?

很顯然，如果計(jì)算一個(gè)類似上圖的遞歸算法，通常就是時(shí)間復(fù)雜度就是O(NlogN)，同樣的，空間復(fù)雜度會(huì)變成O(N)?

（當(dāng)然在面試時(shí)，一般來(lái)說(shuō)遞歸操作時(shí)由操作系統(tǒng)(call stack)自動(dòng)完成，所以一般不會(huì)問(wèn)空間復(fù)雜度）

?

快速排序的偽代碼 （參考https://www.geeksforgeeks.org/quick-sort/）（每個(gè)子問(wèn)題利用雙指針，讓相對(duì)小的放左邊相對(duì)大的放右邊）

// low --> starting index // high --> ending indexquickSort(arr[], low, high) {if (low < high) {/*pi is partitioning index, arr[pi] is now at right place*/pi = partition(arr, low, high)quickSort(arr, low, pi - 1)quickSort(arr, pi + 1, high)}partition(arr[], low, high) {//pivot (Element to be placed at right position)pivot = arr[high];i = low - 1 //index of smaller elementfor (j = low; j <= high - 1; j++) {// If current element is smaller than pivotif (arr[j] < pivot){i++;swap arr[i] and arr[j]}}swap arr[i + 1] and arr[high]return i + 1} }

顯然這是一個(gè)典型的分治算法，和109問(wèn)題有異曲同工之妙

?

---

但是如果看pre-order或dfs遍歷樹(shù)的題目，看似也像一個(gè)分治算法，實(shí)際上只是普通遍歷而已

preorder(root) {if(root) {visit rootpreorder(root.left)preorder(root.right)} }dfs(root) {if(root) {dfs(root.left)visit rootdfs(root.right)} }

和分治算法的區(qū)別就是，他們每次調(diào)用preorder的時(shí)候時(shí)間復(fù)雜度并不是O(n)，而是O(1)

所以很明顯，根據(jù)每個(gè)節(jié)點(diǎn)都被訪問(wèn)一次，他們時(shí)間復(fù)雜度就是O(n)，

但是需要注意的是，空間復(fù)雜度在最壞情況下是O(n)

而在最好情況呢（也就是平衡滿二叉樹(shù)）

以dfs為例，訪問(wèn)時(shí)，占用最大空間的時(shí)候就是綠色圖示的樣子，也就是搜索到第logN層，之后訪問(wèn)一次，離開(kāi)一次，內(nèi)存會(huì)被清理。

所以最好情況下，空間復(fù)雜度就是O(logN)

?

---

?

還需要注意的是，非遍歷算法，且沒(méi)用到分治的情況。

?

如在二分查找樹(shù)（BST）查找到過(guò)程中，時(shí)間復(fù)雜度是O(logN)，很顯然并沒(méi)有用到分治算法，最差情況下就是在樹(shù)的枝葉上找到，也就是O(logN)

總結(jié)

以上是生活随笔為你收集整理的树状结构 - 时间复杂度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。