LeetCode - Medium - 1382. Balance a Binary Search Tree

╰+哭是因爲堅強的太久メ 2022-10-11 13:37 180阅读 0赞

## Topic ##

*  Divide and Conquer
 *  Binary Search Tree
 *  Depth-First Search

## Description ##

[https://leetcode.com/problems/balance-a-binary-search-tree/][https_leetcode.com_problems_balance-a-binary-search-tree]

Given a binary search tree, return a **balanced** binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

**Example 1:**

![aa09485fe37b0b168801fc9a8f0cb879.png][]  
![66547ddf3ee4fe48941d00678e7c72f8.png][]

Input: root = [1,null,2,null,3,null,4,null,null]
    Output: [2,1,3,null,null,null,4]
    Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.

**Constraints:**

*  The number of nodes in the tree is between  1 1 1 and  1 0 4 10^4 104.
 *  The tree nodes will have distinct values between  1 1 1 and  1 0 5 10^5 105.

## Analysis ##

方法一：中序遍历BST，得出节点序列。然后，从序列递归取中节点重制BST。

TODO:方法二：AVL树。

TODO:方法三：DSW算法。

## Submission ##

import java.util.ArrayList;
    import java.util.List;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class BalanceABinarySearchTree { 
    	
        public TreeNode balanceBST(TreeNode root) { 
    		List<TreeNode> list = new ArrayList<>();
    		inorderTraverse(root, list);
        	return remakeBST(list, 0, list.size() - 1);
        }
            
        private void inorderTraverse(TreeNode node, List<TreeNode> list) { 
        	if(node == null) return;
        	inorderTraverse(node.left, list);
        	list.add(node);
        	inorderTraverse(node.right, list);
        }
        
        private TreeNode remakeBST(List<TreeNode> list, int start, int end) { 
        	if(start > end) return null;
        	int mid = start + (end - start) / 2;
        	TreeNode node = list.get(mid);
        	node.left = remakeBST(list, start, mid - 1);
        	node.right = remakeBST(list, mid + 1, end);
        	return node;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class BalanceABinarySearchTreeTest { 
    
        @Test
        public void test() { 
            BalanceABinarySearchTree bObj = new BalanceABinarySearchTree();
            
            TreeNode origin = BinaryTree.of(1,null,2,null,3,null,4,null,null);
            TreeNode expected = BinaryTree.of(2,1,3,null,null,null,4);
            assertTrue(BinaryTree.equals(bObj.balanceBST(origin), expected));
        }
    }

[https_leetcode.com_problems_balance-a-binary-search-tree]: https://leetcode.com/problems/balance-a-binary-search-tree/
[aa09485fe37b0b168801fc9a8f0cb879.png]: /images/20221005/055e2a81e05647ea874d1c2b2e02c3fb.png
[66547ddf3ee4fe48941d00678e7c72f8.png]: /images/20221005/46cc6033c5c744f6972f8826a8926b4a.png