摘要:解法一中序遍歷分析由于給定了二叉搜索樹(shù),因此首先考慮中序遍歷,使用示例,我們先來(lái)分別看一下二叉搜索樹(shù)和累加樹(shù)中序遍歷的結(jié)果二叉搜索樹(shù)二叉累加樹(shù)。這里還是使用示例,我們?cè)賮?lái)觀察一下二叉搜索樹(shù)和累加樹(shù)中序遍歷的結(jié)果二叉搜索樹(shù)二叉累加樹(shù)。
給定一棵二叉搜索樹(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ì):
node.val
小于此節(jié)點(diǎn)的節(jié)點(diǎn);node.val
大于此節(jié)點(diǎn)的節(jié)點(diǎn);
- 輸入:
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]
- 輸入:
root = [0, null, 1]
- 輸出:
[1, null, 1]
- 輸入:
root = [1, 0, 2]
- 輸出:
[3, 3, 2]
- 輸入:
root = [3, 2, 4, 1]
- 輸出:
[7, 9, 4, 10]
- 來(lái)源: 力扣(LeetCode)
- 鏈接: https://leetcode-cn.com/problems/convert-bst-to-greater-tree
由于給定了二叉搜索樹(shù),因此首先考慮中序遍歷,使用示例 1 1 1 ,我們先來(lái)分別看一下二叉搜索樹(shù)和累加樹(shù)中序遍歷的結(jié)果:
bst_inorder = [0, 1, 2, 3, 4, 5, 6, 7, 8]
;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)值。
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()
self._convert_bst
方法被遞歸調(diào)用 n 次,每次都使用了列表的切片操作,而切片操作需要額外的內(nèi)存空間,所以總的內(nèi)存空間為 n + ( n ? 1 ) + ? + 1 n+{(n-1)}+/cdots+1 n+(n?1)+?+1 。實(shí)際上,僅使用一次中序遍歷也可求解本題,而且還更高效。這里還是使用示例 1 1 1 ,我們?cè)賮?lái)觀察一下二叉搜索樹(shù)和累加樹(shù)中序遍歷的結(jié)果:
bst_inorder = [0, 1, 2, 3, 4, 5, 6, 7, 8]
;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ù),這種遍歷方式這里成為反中序遍歷。
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()
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/123722.html
摘要:在線網(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...
摘要:解法二迭代中序遍歷分析作者二叉搜索樹(shù)的中序后繼是中序遍歷中當(dāng)前節(jié)點(diǎn)之后最小的節(jié)點(diǎn)。 文章目錄 1. 題目1.1 示例1.2 說(shuō)明1.3 限制 2....
摘要:文章目錄題目示例說(shuō)明限制解法一分析實(shí)現(xiàn)復(fù)雜度題目給定一棵二叉樹(shù)的根節(jié)點(diǎn),請(qǐng)返回所有的重復(fù)子樹(shù)。示例示例輸入輸出示例輸入輸出示例輸入輸出說(shuō)明來(lái)源力扣鏈接限制二叉樹(shù)中的節(jié)點(diǎn)數(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ì)鏈...
閱讀 3196·2021-11-18 10:02
閱讀 1446·2021-10-12 10:08
閱讀 1236·2021-10-11 10:58
閱讀 1269·2021-10-11 10:57
閱讀 1167·2021-10-08 10:04
閱讀 2121·2021-09-29 09:35
閱讀 773·2021-09-22 15:44
閱讀 1268·2021-09-03 10:30