LeetCode - Medium - 1038. Binary Search Tree to Greater Sum Tree

曾经终败给现在 2022-10-05 04:56 56阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Binary Search Tree
 *  Recursion

## Description ##

[https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/][https_leetcode.com_problems_binary-search-tree-to-greater-sum-tree]

Given the `root` of 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.

As a reminder, a binary search tree is a tree that satisfies these constraints:

*  The left subtree of a node contains only nodes with keys **less than** the node’s key.
 *  The right subtree of a node contains only nodes with keys **greater than** the node’s key.
 *  Both the left and right subtrees must also be binary search trees.

**Note**: This question is the same as 538: [https://leetcode.com/problems/convert-bst-to-greater-tree/][https_leetcode.com_problems_convert-bst-to-greater-tree]

**Example 1:**

![5b5e6e441187c9ffb7a73fcf797e08a0.png][]

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
    Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

**Example 2:**

Input: root = [0,null,1]
    Output: [1,null,1]

**Example 3:**

Input: root = [1,0,2]
    Output: [3,3,2]

**Example 4:**

Input: root = [3,2,4,1]
    Output: [7,9,4,10]

**Constraints:**

*  The number of nodes in the tree is in the range `[1, 100]`.
 *  `0 <= Node.val <= 100`
 *  All the values in the tree are **unique**.
 *  `root` is guaranteed to be a valid binary search tree.

## Analysis ##

方法一：中序遍历模式的递归版

方法二：中序遍历模式的迭代版

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class BinarySearchTreeToGreaterSumTree { 
        
    	//方法一：中序遍历模式的递归版
    	public TreeNode bstToGst(TreeNode root) { 
        	bstToGst(root, new int[] { 0});
    		return root;
        }
        
        private void bstToGst(TreeNode node, int[] sum) { 
        	if(node == null)
        		return;
        	bstToGst(node.right, sum);
        	sum[0] = node.val += sum[0];
        	bstToGst(node.left, sum);
        }
        
        //方法二：中序遍历模式的迭代版
        public TreeNode bstToGst2(TreeNode root) { 
        	TreeNode p = root;
        	LinkedList<TreeNode> stack = new LinkedList<>();
        	int sum = 0;
        	while(!stack.isEmpty() || p != null) { 
        		if(p != null) { 
        			stack.push(p);
        			p = p.right;
        		}else { 
        			TreeNode node = stack.pop();
        			sum = node.val += sum;
        			p = node.left;
        		}
        	}
        	
    		return root;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class BinarySearchTreeToGreaterSumTreeTest { 
    
    	@Test
    	public void test() { 
    		BinarySearchTreeToGreaterSumTree obj = new BinarySearchTreeToGreaterSumTree();
    
    		TreeNode root1 = BinaryTree.integers2BinaryTree(4,1,6,0,2,5,7,null,null,null,3,null,null,null,8);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(30,36,21,36,35,26,15,null,null,null,33,null,null,null,8);
    		assertTrue(BinaryTree.equals(obj.bstToGst(root1), expected1));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(0,null,1);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(1,null,1);
    		assertTrue(BinaryTree.equals(obj.bstToGst(root2), expected2));
    		
    		TreeNode root3 = BinaryTree.integers2BinaryTree(1,0,2);
    		TreeNode expected3 = BinaryTree.integers2BinaryTree(3,3,2);
    		assertTrue(BinaryTree.equals(obj.bstToGst(root3), expected3));
    		
    		TreeNode root4 = BinaryTree.integers2BinaryTree(3,2,4,1);
    		TreeNode expected4 = BinaryTree.integers2BinaryTree(7,9,4,10);
    		assertTrue(BinaryTree.equals(obj.bstToGst(root4), expected4));
    	}
    	
    	@Test
    	public void test2() { 
    		BinarySearchTreeToGreaterSumTree obj = new BinarySearchTreeToGreaterSumTree();
    		
    		TreeNode root1 = BinaryTree.integers2BinaryTree(4,1,6,0,2,5,7,null,null,null,3,null,null,null,8);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(30,36,21,36,35,26,15,null,null,null,33,null,null,null,8);
    		assertTrue(BinaryTree.equals(obj.bstToGst2(root1), expected1));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(0,null,1);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(1,null,1);
    		assertTrue(BinaryTree.equals(obj.bstToGst2(root2), expected2));
    		
    		TreeNode root3 = BinaryTree.integers2BinaryTree(1,0,2);
    		TreeNode expected3 = BinaryTree.integers2BinaryTree(3,3,2);
    		assertTrue(BinaryTree.equals(obj.bstToGst2(root3), expected3));
    		
    		TreeNode root4 = BinaryTree.integers2BinaryTree(3,2,4,1);
    		TreeNode expected4 = BinaryTree.integers2BinaryTree(7,9,4,10);
    		assertTrue(BinaryTree.equals(obj.bstToGst2(root4), expected4));
    	}
    }

[https_leetcode.com_problems_binary-search-tree-to-greater-sum-tree]: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
[https_leetcode.com_problems_convert-bst-to-greater-tree]: https://leetcode.com/problems/convert-bst-to-greater-tree/
[5b5e6e441187c9ffb7a73fcf797e08a0.png]: /images/20221005/89a2620643574f308472c7f60510e314.png