LeetCode - Easy - 897. Increasing Order Search Tree

骑猪看日落 2022-10-06 05:42 14阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Recursion

## Description ##

[https://leetcode.com/problems/increasing-order-search-tree/][https_leetcode.com_problems_increasing-order-search-tree]

Given the `root` of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

**Example 1:**

![49c63754f72223bbb5d72ff45e254d49.png][]

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
    Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

**Example 2:**

![f200f6ef0e0dd228d4539b837d07a704.png][]

Input: root = [5,1,7]
    Output: [1,null,5,null,7]

**Constraints:**

*  The number of nodes in the given tree will be in the range `[1, 100]`.
 *  `0 <= Node.val <= 1000`

## Analysis ##

基本思想：`result = inorder(root.left) + root + inorder(root.right)`

方法一：我写的，递归法

方法二：别人写的，递归法

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class IncreasingOrderSearchTree { 
    	
    	//方法一：我写的，递归法
        public TreeNode increasingBST(TreeNode root) { 
    		if(root == null) return null;
        	
        	TreeNode left = increasingBST(root.left);
        	
        	if(left != null) { 
    	    	TreeNode p = left;
    	    	
    	    	while(p.right != null) { 
    	    		p = p.right;
    	    	}
    	    	
    	    	p.right = root;
        	}
        	
        	root.left = null;
        	root.right = increasingBST(root.right);
        	
        	return left == null ? root : left;
        }
        
        //方法二：别人写的，递归法
        public TreeNode increasingBST2(TreeNode root) { 
            return increasingBST2(root, null);
        }
    
        private TreeNode increasingBST2(TreeNode root, TreeNode tail) { 
            if (root == null) return tail;
            TreeNode res = increasingBST2(root.left, root);
            root.left = null;
            root.right = increasingBST2(root.right, tail);
            return res;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class IncreasingOrderSearchTreeTest { 
    
    	@Test
    	public void test() { 
    		IncreasingOrderSearchTree obj = new IncreasingOrderSearchTree();
    		
    		TreeNode root1 = BinaryTree.integers2BinaryTree(5, 3, 6, 2, 4, null, 8, 1, null, null, null, 7, 9);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(1, null, 2, null, 3, null, 4, null, 5, null, 6, null, 7, null, 8, null, 9);
    		assertTrue(BinaryTree.equals(obj.increasingBST(root1), expected1));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(5, 1, 7);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(1,null,5,null,7);
    		assertTrue(BinaryTree.equals(obj.increasingBST(root2), expected2));
    	}
    	
    	@Test
    	public void test2() { 
    		IncreasingOrderSearchTree obj = new IncreasingOrderSearchTree();
    		
    		TreeNode root1 = BinaryTree.integers2BinaryTree(5, 3, 6, 2, 4, null, 8, 1, null, null, null, 7, 9);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(1, null, 2, null, 3, null, 4, null, 5, null, 6, null, 7, null, 8, null, 9);
    		assertTrue(BinaryTree.equals(obj.increasingBST2(root1), expected1));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(5, 1, 7);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(1,null,5,null,7);
    		assertTrue(BinaryTree.equals(obj.increasingBST2(root2), expected2));
    	}
    }

[https_leetcode.com_problems_increasing-order-search-tree]: https://leetcode.com/problems/increasing-order-search-tree/
[49c63754f72223bbb5d72ff45e254d49.png]: /images/20221005/19c240fc8582453797d2d0953256bf99.png
[f200f6ef0e0dd228d4539b837d07a704.png]: /images/20221005/f9c8664e50fe459fbf714c342fb5cb22.png