LeetCode - Medium - 106. Construct Binary Tree from Inorder and Postorder Traversal

旧城等待， 2022-10-06 15:57 13阅读 0赞

## Topic ##

*  Array
 *  Tree
 *  Depth-first Search

## Description ##

[https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/][https_leetcode.com_problems_construct-binary-tree-from-inorder-and-postorder-traversal]

Given two integer arrays `inorder` and `postorder` where `inorder` is the inorder traversal of a binary tree and `postorder` is the postorder traversal of the same tree, construct and return the binary tree.

**Example 1:**  
![3191074cd189469c9d9199a126b6d035.png][]

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    Output: [3,9,20,null,null,15,7]

**Example 2:**

Input: inorder = [-1], postorder = [-1]
    Output: [-1]

**Constraints:**

*  `1 <= inorder.length <= 3000`
 *  `postorder.length == inorder.length`
 *  `-3000 <= inorder[i], postorder[i] <= 3000`
 *  `inorder` and `postorder` consist of **unique** values.
 *  Each value of `postorder` also appears in `inorder`.
 *  `inorder` is **guaranteed** to be the inorder traversal of the tree.
 *  `postorder` is **guaranteed** to be the postorder traversal of the tree.

## Analysis ##

受[LeetCode - Medium - 105. Construct Binary Tree from Preorder and Inorder Traversal][]启发。

## Submission ##

import java.util.HashMap;
    import java.util.Map;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class ConstructBinaryTreeFromInorderAndPostorderTraversal { 
        public TreeNode buildTree(int[] inorder, int[] postorder) { 
        	Map<Integer, Integer> inMap = new HashMap<>();
        	for(int i = 0; i < inorder.length; i++)
        		inMap.put(inorder[i], i);
        	
        	return buildTree(inorder, 0, inorder.length - 1, // 
        			postorder, 0, postorder.length - 1, inMap);
        }
        
        private TreeNode buildTree(int[] inorder, int inStart, int inEnd, // 
        		int[] postorder, int postStart, int postEnd, Map<Integer, Integer> inMap) { 
        	
        	if(inStart > inEnd || postStart > postEnd) return null;
        	TreeNode parent = new TreeNode(postorder[postEnd]);
        	
        	int parentIndexInInorder = inMap.get(parent.val); 
        	int leftSubtreeNodeNum = parentIndexInInorder - inStart;
        	
        	parent.left = buildTree(inorder, inStart, parentIndexInInorder - 1, // 
        			postorder, postStart, postStart + leftSubtreeNodeNum - 1, inMap);
        	
        	parent.right = buildTree(inorder, parentIndexInInorder + 1, inEnd, // 
        			postorder, postStart + leftSubtreeNodeNum, postEnd - 1, inMap);
        	
        	return parent;
        }
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class ConstructBinaryTreeFromInorderAndPostorderTraversalTest { 
    
    	@Test
    	public void test() { 
    		ConstructBinaryTreeFromInorderAndPostorderTraversal obj = // 
    				new ConstructBinaryTreeFromInorderAndPostorderTraversal();
    
    		TreeNode actual1 = obj.buildTree(new int[] { 9, 3, 15, 20, 7}, //
    				new int[] { 9, 15, 7, 20, 3});
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(3,9,20,null,null,15,7);
    		assertTrue(BinaryTree.equals(actual1, expected1));
    		
    		TreeNode actual2 = obj.buildTree(new int[] { -1}, //
    				new int[] { -1});
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(-1);
    		assertTrue(BinaryTree.equals(actual2, expected2));
    		
    	}
    	
    	
    	
    }

[https_leetcode.com_problems_construct-binary-tree-from-inorder-and-postorder-traversal]: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[3191074cd189469c9d9199a126b6d035.png]: /images/20221005/98511d2122f2497f94088165845df249.png
[LeetCode - Medium - 105. Construct Binary Tree from Preorder and Inorder Traversal]: https://blog.csdn.net/u011863024/article/details/117912485