从中序与后序遍历序列构造二叉树

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param inorder int整型vector 中序遍历序列
     * @param postorder int整型vector 后序遍历序列
     * @return TreeNode类
     */
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // write code here
        if (postorder.empty()) return nullptr;
        TreeNode *root = new TreeNode(postorder[postorder.size() - 1]);
        vector<int> left, right;
        for (int i = 0; i < inorder.size(); ++i) {
            if (inorder[i] == root->val) {
                // left
                vector<int> left_in(inorder.begin(), inorder.begin() + i);
                vector<int> left_post(postorder.begin(), postorder.begin() + i);
                root->left = buildTree(left_in, left_post);
                // right
                vector<int> right_in(inorder.begin() + i + 1, inorder.end());
                vector<int> right_post(postorder.begin() + i, postorder.end() - 1);
                root->right = buildTree(right_in, right_post);
            }
        }
        return root;
    }
};

package main
//import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param inorder int整型一维数组 中序遍历序列
 * @param postorder int整型一维数组 后序遍历序列
 * @return TreeNode类
*/
func buildTree( inorder []int ,  postorder []int ) *TreeNode {
    // write code here
    if len(postorder) == 0{
        return nil
    }
    newNode := new(TreeNode)
    newNode.Val = postorder[len(postorder) - 1]
    for i := 0; i < len(inorder); i++{
        if newNode.Val == inorder[i]{
            newNode.Left = buildTree(inorder[:i], postorder[:i])
            newNode.Right = buildTree(inorder[i+1:], postorder[i:len(postorder)-1])
            return newNode
        }
    }
    return newNode
}

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // write code here
        if(inorder.size()==0||postorder.size()==0) return nullptr;
        int x=*postorder.rbegin();
        TreeNode *root=new TreeNode(x);
        int post;
        for(int i=0;i<inorder.size();i++)
        {
            if(inorder[i]==x) post=i;
        }
        vector<int> lin;
        vector<int> rin;
        for(int i=0;i<post;i++) lin.push_back(inorder[i]);
        for(int i=post+1;i<inorder.size();i++) rin.push_back(inorder[i]);
        vector<int>lpost;
        vector<int>rpost;
        for(int i=0;i<post;i++)lpost.push_back(postorder[i]);
        for(int i=post;i<postorder.size()-1;i++)rpost.push_back(postorder[i]);
        root->left=buildTree(lin, lpost);
        root->right=buildTree(rin, rpost);
        return root;
    }

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param inorder int整型一维数组 中序遍历序列
     * @param postorder int整型一维数组 后序遍历序列
     * @return TreeNode类
     */
    public TreeNode buildTree (int[] inorder, int[] postorder) {
        // write code here
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
    // 左 中 右
    // 左 右 中
    private TreeNode build(int[] inOrder, int li, int ri, int[] postorder, int lp, int rp) {
        if(li > ri) return null;
        TreeNode cur = new TreeNode(postorder[rp]);
        int i = li;
        for(; i <= ri; i++) {
            if(inOrder[i] == postorder[rp]) break;
        }
        cur.left = build(inOrder, li, i - 1,  postorder, lp, lp + i  - li - 1);
        // ri - i - 1
        cur.right = build(inOrder, i + 1, ri, postorder, rp - ri + i, rp - 1);
        return cur;

    }
}

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode* left;
 *	struct TreeNode* right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
    int post_idx;  // 从后序遍历的 最后一个元素开始
    unordered_map<int, int> idx_map;// 建立（中序元素，后序下标）键值对的哈希表
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size()-1;
        int idx = 0;  // 建立（中序元素，中序下标）键值对的哈希表
        for (auto& val : inorder) 
            idx_map[val] = idx++;
        return helper(0, (int)inorder.size()-1, inorder, postorder);
    }
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){  
        if (in_left > in_right) // 如果这里没有节点构造二叉树了，就结束
            return nullptr;
        int root_val = postorder[post_idx]; //1 选择post_idx位置的元素，作为当前子树 根节点
        post_idx--; // 下标减一 
        TreeNode* root = new TreeNode(root_val); // 根节点

        int index = idx_map[root_val];      //2 根据root所在中序的index，将中序分成左右两棵子树

        root->right = helper(index+1, in_right,  inorder, postorder); // 1构造root节点的右子树
        root->left  = helper(in_left,   index-1, inorder, postorder); // 2构造root节点的左子树
        return root; // 根节点
    }
};

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param inorder int整型一维数组 中序遍历序列
 * @param postorder int整型一维数组 后序遍历序列
 * @return TreeNode类
 */
function buildTree( inorder ,  postorder ) {
    if(postorder.length==0) return null;
    let root_val=postorder[postorder.length-1];
    let idx=inorder.indexOf(root_val);
    let root=new TreeNode(root_val);
    root.left=buildTree(inorder.slice(0,idx),postorder.slice(0,idx));
    root.right=buildTree(inorder.slice(idx+1),postorder.slice(idx,postorder.length-1));
    return root;
}
module.exports = {
    buildTree : buildTree
};

Map<Integer, Integer> inOrderMap;
int[] postOrder;
int postIdx;

public TreeNode buildTree(int[] inorder, int[] postorder) {
    // 将中序下标放入Map中
    Map<Integer, Integer> inOrderMap = new HashMap<>();
    for (int i=0; i<inorder.length; i++) {
        inOrderMap.put(inorder[i], i);
    }
    this.inOrderMap = inOrderMap;
    this.postIdx = postorder.length-1;
    this.postOrder = postorder;
    return build(0, inorder.length-1);
}

public TreeNode build(int leftIdx, int rightIdx) {
    if (leftIdx > rightIdx) {
        return null;
    }
    int rootVal = postOrder[postIdx--];
    int rootIdx = inOrderMap.get(rootVal);
    TreeNode root = new TreeNode(rootVal);
    // 通过后序遍历往前推，所以先处理右子树
    // 中序遍历，root点的右边是右子树，左边是左子树
    root.right = build(rootIdx+1, rightIdx);
    root.left = build(leftIdx, rootIdx-1);
    return root;
}

typedef struct TreeNode TreeNode;
TreeNode* tree(int* inorder, int inL,int inR, int* postorder, int postL,int postR);

struct TreeNode* buildTree(int* inorder, int inorderLen, int* postorder, int postorderLen ) {
    // write code here
    return tree(inorder,0,inorderLen-1,postorder,0,postorderLen-1);
    
}

//递归法构造
TreeNode* tree(int* inorder, int inL,int inR, int* postorder, int postL,int postR)
{
    if(postL>postR)
        return NULL;
    
    TreeNode* node = malloc(sizeof(TreeNode));
    node->val=postorder[postR];
    int pos = inL;
    while(pos<=inR && inorder[pos]!=node->val)
    {
        ++pos;
    }
    node->left = tree(inorder, inL, pos-1, postorder, postL, postL+pos-inL-1);
    node->right = tree(inorder, pos+1, inR, postorder, postL+pos-inL, postR-1);
    return node;
}

    int[] post;
    HashMap<Integer,Integer> inorderMap = new HashMap<Integer,Integer>();
    public TreeNode buildTree (int[] inorder, int[] postorder) {
       for(int i = 0;i<inorder.length;i++){
           inorderMap.put(inorder[i],i);
       }
        // write code here
        post = postorder;
        int len = inorder.length;
        
        return build(0,len - 1,0,len -1);
    }
    private TreeNode build(int inleft,int inright,int postleft,int postright){
        if(inleft > inright || postleft > postright){
            return null;
        }
        int value = post[postright];
        int index = inorderMap.get(value);
        TreeNode root = new TreeNode(value);
        root.left = build(inleft,index - 1,postleft,postleft+index-inleft -1);
        root.right = build(index+1,inright,postleft+index-inleft,postright -1);
        return root;
    }

class Solution:
    def buildTree(self , inorder: List[int], postorder: List[int]) -> TreeNode:
        # write code here
        if postorder:
            ind=inorder.index(postorder[-1])
            root=TreeNode(postorder.pop())
            root.left=self.buildTree(inorder[:ind],postorder[:ind])#左都同
            root.right=self.buildTree(inorder[ind+1:],postorder[ind:])
            return root