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:

1
2
3
4
5
6
7
8
9
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

分析

题意是对于一颗二叉树做加法转换，对于每棵树，根节点的值等于右节点的值加上根节点的值，左节点的值等于父节点的值加上右节点的值加上自身的值，可以看出来应该按照右节点，父节点，左节点的顺序叠加，也就是说是一种中序遍历，但顺序有些不同，应该按照右中左的顺序遍历二叉树。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
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

题目来源