LeetCode—106. Construct Binary Tree from Inorder and Postorder Traversal

LeetCode—106. Construct Binary Tree from Inorder and Postorder Traversal

题目

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
中序遍历和后序遍历确定二叉树。注意二叉树中不存在重复元素。

思路及解法

解法与LeetCode—105. Construct Binary Tree from Preorder and Inorder Traversal相似。
后序遍历确定根节点，中序遍历确定左右子树。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);
    }
    public TreeNode helper(int[] inorder, int[] postorder, int instart, int inend, int posstart, int posend){
        if(instart>inend || posstart>posend) return null;
        TreeNode node = new TreeNode(postorder[posend]);
        int index = 0;
        for(int i=instart; i<=inend; i++){
            if(inorder[i]==postorder[posend]){
                index = i;
                break;
            }
        }
        node.right=helper(inorder, postorder, index+1, inend, posend-inend+index, posend-1);
        node.left=helper(inorder, postorder, instart, index-1, posstart, posend-inend+index-1);
        return node;
    }
}