Shulou(Shulou.com)06/02 Report--

This article mainly introduces how to convert the binary search tree into a cumulative tree in Java, which has a certain reference value, and interested friends can refer to it. I hope you will gain a lot after reading this article.

I. title

The root node of the binary search tree is given, and the node values of the tree are different. Please convert it into a cumulative tree (Greater Sum Tree) so that the new value of node of each node is equal to the sum of values greater than or equal to node.val in the original tree.

As a reminder, the binary search tree meets the following constraints:

The left subtree of a node contains only nodes whose keys are less than the node keys.

The right subtree of a node contains only nodes whose keys are greater than the node keys.

The left and right subtrees must also be binary search trees.

Second, answer the question.

Looking at the example diagram, it is found that the traversal order of the tree is right, middle and left, and the value of each node is the cumulative state in this order.

Because it needs to be accumulated, the pre pointer is required to record the previous node of the current traversal node cur to facilitate accumulation.

(1) determine the recursive function and return value

The topic needs to traverse the whole tree and define a global variable pre, which is used to hold the value of the previous node of the cur node.

(2) determine the conditions for recursive termination.

Terminate when you encounter an empty space

(3) determine the logic of single-layer recursion.

The order of traversing, right, middle, left

Code class Solution {/ / record precursor node int pre = 0; public TreeNode convertBST (TreeNode root) {/ / empty node termination if (root = = null) {return root;} / / traversal order: right, middle, left convertBST (root.right); root.val + = pre; pre = root.val ConvertBST (root.left); return root;}} Thank you for reading this article carefully. I hope the article "how to convert a binary search tree into a cumulative tree in Java" shared by the editor will be helpful to you. At the same time, I also hope you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.