国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

【LeetCode 二叉樹(shù)專項(xiàng)】把二叉搜索樹(shù)轉(zhuǎn)換為累加樹(shù)(538)

xcold / 3195人閱讀

摘要:解法一中序遍歷分析由于給定了二叉搜索樹(shù),因此首先考慮中序遍歷,使用示例,我們先來(lái)分別看一下二叉搜索樹(shù)和累加樹(shù)中序遍歷的結(jié)果二叉搜索樹(shù)二叉累加樹(shù)。這里還是使用示例,我們?cè)賮?lái)觀察一下二叉搜索樹(shù)和累加樹(shù)中序遍歷的結(jié)果二叉搜索樹(shù)二叉累加樹(shù)。

1. 題目

給定一棵二叉搜索樹(shù)(Binary Search Tree: BST)的根節(jié)點(diǎn) root ,請(qǐng)將其轉(zhuǎn)化為一棵累加樹(shù),所謂的累加樹(shù)和原二叉搜索樹(shù)在結(jié)構(gòu)上完全一樣;不同的是對(duì)應(yīng)位置節(jié)點(diǎn)的值不同,即累加樹(shù)上每個(gè)節(jié)點(diǎn)的值 node.val 是原二叉搜索樹(shù)所有大于或等于 node.val 的節(jié)點(diǎn)值之和。

需要注意的是,二叉搜索樹(shù)具有下列性質(zhì):

  • 任意節(jié)點(diǎn)的左子樹(shù)僅包含 node.val 小于此節(jié)點(diǎn)的節(jié)點(diǎn);
  • 任意節(jié)點(diǎn)的右子樹(shù)僅包含 node.val 大于此節(jié)點(diǎn)的節(jié)點(diǎn);
  • 左右子樹(shù)也必須是二叉搜索樹(shù)。

1.1 示例

  • 示例 1 1 1
  • 輸入: root = [4, 1, 6, 0, 2, 5, 7, null, null, null, 3, null, null, null, 8]
  • 輸出: [30, 36, 21, 36, 35, 26, 15, null, null, null, 33, null, null, null, 8]

  • 示例 2 2 2
  • 輸入: root = [0, null, 1]
  • 輸出: [1, null, 1]
  • 示例 3 3 3
  • 輸入: root = [1, 0, 2]
  • 輸出: [3, 3, 2]
  • 示例 4 4 4
  • 輸入: root = [3, 2, 4, 1]
  • 輸出: [7, 9, 4, 10]

1.2 說(shuō)明

1.3 限制

  • 樹(shù)中的節(jié)點(diǎn)數(shù)介于 0 0 0 1 0 4 10^4 104 之間;
  • 每個(gè)節(jié)點(diǎn)的值介于 ? 1 0 4 -10^4 ?104 1 0 4 10^4 104 之間;
  • 樹(shù)中的所有值互不相同 ;
  • 給定的樹(shù)為二叉搜索樹(shù)。

2. 解法一(中序遍歷)

2.1 分析

由于給定了二叉搜索樹(shù),因此首先考慮中序遍歷,使用示例 1 1 1 ,我們先來(lái)分別看一下二叉搜索樹(shù)和累加樹(shù)中序遍歷的結(jié)果:

  • 二叉搜索樹(shù): bst_inorder = [0, 1, 2, 3, 4, 5, 6, 7, 8]
  • 二叉累加樹(shù): gbt_inorder = [36, 36, 35, 33, 30, 26, 21, 15, 8]

通過(guò)觀察不難發(fā)現(xiàn): gbt_inorder[i] = sum(bst_inorder[i:]) ,其中: 0 <= i < len(bst_inorder)

因此,本體可以通過(guò)兩次中序遍歷來(lái)求解,第一次得到二叉搜索樹(shù)的中序便利序列;第二次填充累加樹(shù)的各個(gè)節(jié)點(diǎn)值。

2.2 實(shí)現(xiàn)

from collections import dequefrom typing import Optionalclass TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass Solution:    def __init__(self):        self._tree = []        self._counter = 0    def _inorder_traverse(self, root: Optional[TreeNode]):        if not root:            return        self._inorder_traverse(root.left)        self._tree.append(root.val)        self._inorder_traverse(root.right)    def _convert_bst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:        if not root:            return        self._convert_bst(root.left)        root.val = sum(self._tree[self._counter:])        self._counter += 1        self._convert_bst(root.right)    def convert_bst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:        self._inorder_traverse(root)        self._convert_bst(root)        return rootdef main():    node9 = TreeNode(8)    node8 = TreeNode(3)    node7 = TreeNode(7, right=node9)    node6 = TreeNode(5)    node5 = TreeNode(2, right=node8)    node4 = TreeNode(0)    node3 = TreeNode(6, left=node6, right=node7)    node2 = TreeNode(1, left=node4, right=node5)    node1 = TreeNode(4, left=node2, right=node3)    root = node1    sln = Solution()    sln.convert_bst(root)    tree = []    visiting = deque([root])    while visiting:        node = visiting.popleft()        if node:            tree.append(node.val)            visiting.append(node.left)            visiting.append(node.right)        else:            tree.append(None)    while True:        if not tree[-1]:            tree.pop()        else:            break    print(tree)  # [30, 36, 21, 36, 35, 26, 15, None, None, None, 33, None, None, None, 8]if __name__ == "__main__":    main()

2.3 復(fù)雜度

  • 時(shí)間復(fù)雜度: O ( n ) O(n) O(n),其中 n n n 是二叉搜索樹(shù)的節(jié)點(diǎn)數(shù)。每一個(gè)節(jié)點(diǎn)被遍歷兩次;
  • 空間復(fù)雜度: O ( n 2 ) O(n^2) O(n2),由于 self._convert_bst 方法被遞歸調(diào)用 n 次,每次都使用了列表的切片操作,而切片操作需要額外的內(nèi)存空間,所以總的內(nèi)存空間為 n + ( n ? 1 ) + ? + 1 n+{(n-1)}+/cdots+1 n+(n?1)+?+1

3. 解法二(反中序遍歷)

3.1 分析

實(shí)際上,僅使用一次中序遍歷也可求解本題,而且還更高效。這里還是使用示例 1 1 1 ,我們?cè)賮?lái)觀察一下二叉搜索樹(shù)和累加樹(shù)中序遍歷的結(jié)果:

  • 二叉搜索樹(shù): bst_inorder = [0, 1, 2, 3, 4, 5, 6, 7, 8]
  • 二叉累加樹(shù): gbt_inorder = [36, 36, 35, 33, 30, 26, 21, 15, 8]

實(shí)際上,如希望通過(guò) bst_inorder 序列來(lái)得到 gbt_inorder 序列,更直觀的方式應(yīng)該是:

gbt_inorder[8] = bst_inorder[8] = 8gbt_inorder[7] = bst_inorder[8] + bst_inorder[7] = 15gbt_inorder[6] = bst_inorder[8] + bst_inorder[7] + bst_inorder[6] = 21......

之所以一開(kāi)始沒(méi)有使用上面的方式來(lái)求解,原因在于使用二叉樹(shù)的中序遍歷時(shí),獲取 bst_inorder 元素的順序和上述所需的順序是相反的,即上述希望通過(guò) bst_inorder[8]bst_inorder[7] ? /cdots ?bst_inorder[0] 這樣的順序獲得元素,實(shí)際中序遍歷順序卻是 bst_inorder[0]bst_inorder[1] ? /cdots ?bst_inorder[8] 這樣的順序。

實(shí)際上,想要通過(guò)滿足上述要求的方式得到 bst_inorder 的元素序列也很簡(jiǎn)單,只要稍微調(diào)整一下中序遍歷,即按照 右子樹(shù) -> 根節(jié)點(diǎn) -> 左子樹(shù) 這樣的順序來(lái)遍歷二叉樹(shù)搜索樹(shù),這種遍歷方式這里成為反中序遍歷。

3.2 實(shí)現(xiàn)

from collections import dequefrom typing import Optionalclass TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = rightclass Solution:    def __init__(self):        self._total = 0    def _reverse_inorder(self, root: Optional[TreeNode]):        if not root:            return        self._reverse_inorder(root.right)        self._total += root.val        root.val = self._total        self._reverse_inorder(root.left)    def convert_bst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:        self._reverse_inorder(root)        return rootdef main():    node9 = TreeNode(8)    node8 = TreeNode(3)    node7 = TreeNode(7, right=node9)    node6 = TreeNode(5)    node5 = TreeNode(2, right=node8)    node4 = TreeNode(0)    node3 = TreeNode(6, left=node6, right=node7)    node2 = TreeNode(1, left=node4, right=node5)    node1 = TreeNode(4, left=node2, right=node3)    root = node1    sln = Solution()    sln.convert_bst(root)    tree = []    visiting = deque([root])    while visiting:        node = visiting.popleft()        if node:            tree.append(node.val)            visiting.append(node.left)            visiting.append(node.right)        else:            tree.append(None)    while True:        if not tree[-1]:            tree.pop()        else:            break    print(tree)  # [30, 36, 21, 36, 35, 26, 15, None, None, None, 33, None, None, None, 8]if __name__ == "__main__":    main()

3.3 復(fù)雜度

  • 時(shí)間復(fù)雜度: O ( n ) O(n) O(n),其中 n n n 是二叉搜索樹(shù)的節(jié)點(diǎn)數(shù)。每一個(gè)節(jié)點(diǎn)恰好被遍歷一次;
  • 空間復(fù)雜度: O ( n ) O(n) O(n),為遞歸過(guò)程中棧的開(kāi)銷,平均情況下為 O ( log ? n ) O(/log n) O(logn) ,最壞情況下樹(shù)呈現(xiàn)鏈狀,為 O ( n ) O(n) O(n)

4. 解法三(Morris 遍歷)

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/123722.html

相關(guān)文章

  • 前端 | 每天一個(gè) LeetCode

    摘要:在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目,語(yǔ)言 JavaScript。 在線網(wǎng)站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號(hào): showImg(htt...

    張漢慶 評(píng)論0 收藏0
  • LeetCode 樹(shù)專項(xiàng)二叉搜索樹(shù)中的中序后繼(285)

    摘要:解法二迭代中序遍歷分析作者二叉搜索樹(shù)的中序后繼是中序遍歷中當(dāng)前節(jié)點(diǎn)之后最小的節(jié)點(diǎn)。 文章目錄 1. 題目1.1 示例1.2 說(shuō)明1.3 限制 2....

    ccj659 評(píng)論0 收藏0
  • LeetCode 樹(shù)專項(xiàng)】尋找重復(fù)的子樹(shù)(652)

    摘要:文章目錄題目示例說(shuō)明限制解法一分析實(shí)現(xiàn)復(fù)雜度題目給定一棵二叉樹(shù)的根節(jié)點(diǎn),請(qǐng)返回所有的重復(fù)子樹(shù)。示例示例輸入輸出示例輸入輸出示例輸入輸出說(shuō)明來(lái)源力扣鏈接限制二叉樹(shù)中的節(jié)點(diǎn)數(shù)量在之間。 ...

    leejan97 評(píng)論0 收藏0
  • js數(shù)據(jù)結(jié)構(gòu)-樹(shù)二叉搜索樹(shù)

    摘要:前言可能有一部分人沒(méi)有讀過(guò)我上一篇寫(xiě)的二叉堆,所以這里把二叉樹(shù)的基本概念復(fù)制過(guò)來(lái)了,如果讀過(guò)的人可以忽略前面針對(duì)二叉樹(shù)基本概念的介紹,另外如果對(duì)鏈表數(shù)據(jù)結(jié)構(gòu)不清楚的最好先看一下本人之前寫(xiě)的數(shù)據(jù)結(jié)構(gòu)鏈表二叉樹(shù)二叉樹(shù)是一種樹(shù)形結(jié)構(gòu),它的特點(diǎn)是 前言 可能有一部分人沒(méi)有讀過(guò)我上一篇寫(xiě)的二叉堆,所以這里把二叉樹(shù)的基本概念復(fù)制過(guò)來(lái)了,如果讀過(guò)的人可以忽略前面針對(duì)二叉樹(shù)基本概念的介紹,另外如果對(duì)鏈...

    codeKK 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<