题目描述:
LeetCode 538. Convert BST to Greater Tree
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:
Input: The root of a Binary Search Tree like this: 5 / \ 2 13 Output: The root of a Greater Tree like this: 18 / \ 20 13
题目大意:
给定一棵二叉查找树(BST),将其转化为“Greater Tree”,原始BST中的每一个节点都替换为不小于其本身的各节点的和。
解题思路:
“右 - 根 - 左”顺序遍历BST
Python代码:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
self.total = 0
def traverse(root):
if not root: return
traverse(root.right)
root.val += self.total
self.total = root.val
traverse(root.left)
traverse(root)
return root
本文链接:http://bookshadow.com/weblog/2017/03/19/leetcode-convert-bst-to-greater-tree/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。