BST 를 Greater Tree 문제 풀이 보고서 (Python) 로 변환

저자: 음 설 명 초 id: fuxuemingzhu 개인 블 로그:http://fuxuemingzhu.cn/
목차
제목 설명
제목
풀이 방법
귀속
날짜
제목 주소:https://leetcode.com/problems/convert-bst-to-greater-tree/description/
제목 설명
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 의 각 노드 의 값 을 그것 보다 큰 노드 의 값 과 합 으로 다시 설정 합 니 다.
문제 풀이 방법
귀착 하 다
이 문 제 는 각 노드 를 이 노드 보다 큰 (포함) 모든 노드 의 합 으로 바 꿔 야 한다.
이 문제 의 동 기 는 우리 가 먼저 수치 가 비교적 큰 노드 를 수정 한 다음 에 수치 가 비교적 작은 노드 를 수정 해 야 한 다 는 것 이다.이렇게 해야만 우리 가 한 번 에 옮 겨 다 니 기만 하면 모든 노드 의 값 을 그것 보다 더 큰 모든 노드 의 합 으로 수정 할 수 있다 는 것 을 보증 할 수 있다.
BST 의 오른쪽 트 리 는 모두 이 노드 보다 크기 때문에 수정 순 서 는 오른쪽 – > 중 – > 왼쪽 입 니 다.하나의 변수 로 옮 겨 다 니 는 과정 에서 모든 노드 의 합 을 저장 하면 현재 이 노드 의 값 보다 더 큰 합 을 얻 은 다음 에 이 변수의 값 으로 수정 하면 됩 니 다.

# 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.sum = 0
        def afterOrder(cur):
            if not cur: return
            afterOrder(cur.right)
            self.sum += cur.val
            cur.val = self.sum
            afterOrder(cur.left)
        afterOrder(root)
        return root

날짜.
2018 년 1 월 22 일 2018 년 11 월 13 일 - 시간 이 좀 빨 라 요