[数据结构与算法]哈希表——由中序和后序序列构建二叉树

一、递归法

后序序列最后一个就是根节点，再在中序序列中定位根节点.......

Java:这里要把两个数组和postRight定义为成员变量，这样就不用一直传参了。如果当作参数传递的话，会超出时间限制。C++需要定义数组的时候需要指明大小，所以这里c++数组还是当参数传递的。 注意：要先构建右子树，再构建左子树，原因我也没太理解.........

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int postRight;
    int[] postorder;
    int[] inorder;
    private Map<Integer,Integer> indexMap;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder=postorder;
        this.inorder=inorder;
        postRight=postorder.length-1;
        indexMap=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            indexMap.put(inorder[i],i);
        }
        return mybuildTree(0,inorder.length-1);
    }
    public TreeNode mybuildTree(int inLeft,int inRight){
        if(inLeft>inRight) return null;
        TreeNode root=new TreeNode(postorder[postRight]);
        int inRootIndex=indexMap.get(postorder[postRight]);
        postRight--;
        root.right=mybuildTree(inRootIndex+1,inRight);
        root.left=mybuildTree(inLeft,inRootIndex-1);
        return root;
    }
}

?C++：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int postRight;
    int[] postorder;
    int[] inorder;
    private Map<Integer,Integer> indexMap;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder=postorder;
        this.inorder=inorder;
        postRight=postorder.length-1;
        indexMap=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            indexMap.put(inorder[i],i);
        }
        return mybuildTree(0,inorder.length-1);
    }
    public TreeNode mybuildTree(int inLeft,int inRight){
        if(inLeft>inRight) return null;
        TreeNode root=new TreeNode(postorder[postRight]);
        int inRootIndex=indexMap.get(postorder[postRight]);
        postRight--;
        root.right=mybuildTree(inRootIndex+1,inRight);
        root.left=mybuildTree(inLeft,inRootIndex-1);
        return root;
    }
}

二、迭代，用栈

后序的翻转是：根右左? ? ? ? ? ?类似先序

中序的翻转是：右根左?

与由先序中序求二叉树的区别：先是右子树，再是左子树。并且从数组最后开始往前遍历。

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder==null||inorder.length==0) return null;
        Deque<TreeNode> stack=new LinkedList<>();
        TreeNode root=new TreeNode(postorder[postorder.length-1]);
        int inorderIndex=inorder.length-1;
        stack.push(root);
        for(int i=postorder.length-2;i>=0;i--){
            TreeNode node=stack.peek();
            if(inorder[inorderIndex]!=node.val){
                node.right=new TreeNode(postorder[i]);
                stack.push(node.right);
            }
            else{
                while(!stack.isEmpty()&&inorder[inorderIndex]==stack.peek().val){
                    node=stack.pop();
                    inorderIndex--;
                }
                node.left=new TreeNode(postorder[i]);
                stack.push(node.left);
            }
        }
        return root;
    }
    
}

?C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.size()==0) return nullptr;
        stack<TreeNode*> sta;
        int inorderIndex=inorder.size()-1;
        TreeNode* root=new TreeNode(postorder[postorder.size()-1]);
        sta.push(root);
        for(int i=postorder.size()-2;i>=0;i--){
            TreeNode* node=sta.top();
            if(node->val!=inorder[inorderIndex]){
                node->right=new TreeNode(postorder[i]);
                sta.push(node->right);
            }
            else{
                while(!sta.empty()&&inorder[inorderIndex]==sta.top()->val){
                    node=sta.top();
                    sta.pop();
                    inorderIndex--;
                }
                node->left=new TreeNode(postorder[i]);
                sta.push(node->left);
            }
        }
        return root;
    }
};