LeetCode - Medium - 1008. Construct Binary Search Tree from Preorder Traversal

川长思鸟来 2022-10-08 02:19 5阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/][https_leetcode.com_problems_construct-binary-search-tree-from-preorder-traversal]

Given an array of integers preorder, which represents the **preorder traversal** of a BST (i.e., **binary search tree**), construct the tree and return its root.

It is **guaranteed** that there is always possible to find a binary search tree with the given requirements for the given test cases.

A **binary search tree** is a binary tree where for every node, any descendant of `Node.left` has a value **strictly less than** `Node.val`, and any descendant of `Node.right` has a value **strictly greater than** `Node.val`.

A preorder traversal of a binary tree displays the value of the node first, then traverses `Node.left`, then traverses `Node.right`.

**Example 1:**  
![ac72cfac8a9c658760a415a98fba3d17.png][]

Input: preorder = [8,5,1,7,10,12]
    Output: [8,5,10,1,7,null,12]

**Example 2:**

Input: preorder = [1,3]
    Output: [1,null,3]

**Constraints:**

*   1 < = p r e o r d e r . l e n g t h < = 100 1 <= preorder.length <= 100 1<=preorder.length<=100
 *   1 < = p r e o r d e r \[ i \] < = 1 0 8 1 <= preorder\[i\] <= 10^8 1<=preorder\[i\]<=108
 *  All the values of `preorder` are **unique**.

## Analysis ##

方法一：自己写的，受[LeetCode - Medium - 106. Construct Binary Tree from Inorder and Postorder Traversal][]启发。

方法二：别人写的，直接用BST插入写法，没有比这更简单的。

方法三：别人写的，边界很隐晦的样子。

## Submission ##

import com.lun.util.BinaryTree.TreeNode;
    
    public class ConstructBinarySearchTreeFromPreorderTraversal { 
    	
    	//方法一：自己写的
        public TreeNode bstFromPreorder(int[] preorder) { 
            return bstFromPreorder(preorder, 0, preorder.length - 1);
        }
        
        private TreeNode bstFromPreorder(int[] preorder, int start, int end) { 
        	if(start > end) return null;
        	
        	TreeNode parent = new TreeNode(preorder[start]);
        	
        	//binary search
        	int boundary = start;
        	int left = boundary + 1, right = end; 
        	
        	while(left <= right) { 
        		int mid = left + (right - left) / 2;
        		if(preorder[mid] < parent.val) { 
        			if(mid + 1 > end || preorder[mid + 1] > parent.val) { 
        				boundary = mid;
        				break;
        			}
        			left = mid + 1;
        		}else { 
        			right = mid - 1;
        		}
        	}
        	
        	parent.left = bstFromPreorder(preorder, start + 1, boundary);
        	parent.right = bstFromPreorder(preorder, boundary + 1, end);
        	
        	return parent;
        }
        
    
        //方法二：别人写的1，直接用BST插入写法，没有比这更简单的
        public TreeNode bstFromPreorder2(int[] preorder) {  
        	TreeNode root = null;
        	for(int val : preorder) 
        		root = insert(root, val);
        	return root;
        }
        
        private TreeNode insert(TreeNode root, int val) { 
        	
        	if(root == null) 
        		return new TreeNode(val);
        	else if(root.val > val) 
        		root.left = insert(root.left, val);
        	else 
        		root.right = insert(root.right, val);
        	return root;
        }
        
        
        //方法三：别人写的2，边界很隐晦的样子
        public TreeNode bstFromPreorder3(int[] A) { 
            return bstFromPreorder(A, Integer.MAX_VALUE, new int[]{ 0});
        }
    
        public TreeNode bstFromPreorder(int[] A, int bound, int[] i) { 
            if (i[0] == A.length || A[i[0]] > bound) return null;
            TreeNode root = new TreeNode(A[i[0]++]);
            root.left = bstFromPreorder(A, root.val, i);
            root.right = bstFromPreorder(A, bound, i);
            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 ConstructBinarySearchTreeFromPreorderTraversalTest { 
    
    	@Test
    	public void test() { 
    		ConstructBinarySearchTreeFromPreorderTraversal obj = new ConstructBinarySearchTreeFromPreorderTraversal();
    
    		TreeNode expected = BinaryTree.integers2BinaryTree(8, 5, 10, 1, 7, null, 12);
    		TreeNode actual = obj.bstFromPreorder(new int[] { 8, 5, 1, 7, 10, 12});
    		assertTrue(BinaryTree.equals(expected, actual));
    		
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(1, null, 3);
    		TreeNode actual2 = obj.bstFromPreorder(new int[] { 1, 3});
    		assertTrue(BinaryTree.equals(expected2, actual2));
    	}
    	
    	@Test
    	public void test2() { 
    		ConstructBinarySearchTreeFromPreorderTraversal obj = new ConstructBinarySearchTreeFromPreorderTraversal();
    		
    		TreeNode expected = BinaryTree.integers2BinaryTree(8, 5, 10, 1, 7, null, 12);
    		TreeNode actual = obj.bstFromPreorder2(new int[] { 8, 5, 1, 7, 10, 12});
    		assertTrue(BinaryTree.equals(expected, actual));
    		
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(1, null, 3);
    		TreeNode actual2 = obj.bstFromPreorder2(new int[] { 1, 3});
    		assertTrue(BinaryTree.equals(expected2, actual2));
    	}
    	
    	@Test
    	public void test3() { 
    		ConstructBinarySearchTreeFromPreorderTraversal obj = new ConstructBinarySearchTreeFromPreorderTraversal();
    		
    		TreeNode expected = BinaryTree.integers2BinaryTree(8, 5, 10, 1, 7, null, 12);
    		TreeNode actual = obj.bstFromPreorder3(new int[] { 8, 5, 1, 7, 10, 12});
    		assertTrue(BinaryTree.equals(expected, actual));
    		
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(1, null, 3);
    		TreeNode actual2 = obj.bstFromPreorder3(new int[] { 1, 3});
    		assertTrue(BinaryTree.equals(expected2, actual2));
    	}
    }

[https_leetcode.com_problems_construct-binary-search-tree-from-preorder-traversal]: https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/
[ac72cfac8a9c658760a415a98fba3d17.png]: /images/20221005/c9f7c4830508476986cc4fb5dac6bdbd.png
[LeetCode - Medium - 106. Construct Binary Tree from Inorder and Postorder Traversal]: https://blog.csdn.net/u011863024/article/details/117913714