LeetCode in Net
106. Construct Binary Tree from Inorder and Postorder Traversal
Medium
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:
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 <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorderandpostorderconsist of unique values.- Each value of
postorderalso appears ininorder. inorderis guaranteed to be the inorder traversal of the tree.postorderis guaranteed to be the postorder traversal of the tree.
Solution
using LeetCodeNet.Com_github_leetcode;
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public TreeNode BuildTree(int[] inorder, int[] postorder) {
int inIndex = inorder.Length - 1;
int postIndex = postorder.Length - 1;
return Helper(inorder, postorder, ref inIndex, ref postIndex, int.MaxValue);
}
private TreeNode Helper(int[] inorder, int[] postorder, ref int inIndex, ref int postIndex, int target) {
if (inIndex < 0 || inorder[inIndex] == target) {
return null;
}
TreeNode root = new TreeNode(postorder[postIndex--]);
root.right = Helper(inorder, postorder, ref inIndex, ref postIndex, (int)root.val);
inIndex--;
root.left = Helper(inorder, postorder, ref inIndex, ref postIndex, target);
return root;
}
}