LeetCode刷题（C++）——Construct Binary Tree from Inorder and Postorder Traversal（Normal）

阳光穿透心脏的1/2处 2022-06-15 22:52 82阅读 0赞

## 题目描述 ##

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            if (inorder.size() == 0 || postorder.size() == 0 || inorder.size() != postorder.size())
    			return NULL;
    		return dfs(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
    	}
    
    	TreeNode* dfs(vector<int>&inorder, int l1, int r1, vector<int>& postorder, int l2, int r2)
    	{
    		if (l2 > r2)
    			return NULL;
    		if (l2 == r2)
    			return new TreeNode(postorder[r2]);
    		TreeNode* root = new TreeNode(postorder[r2]);
    		for (int i = 0; i < inorder.size();i++)
    		{
    			if (inorder[i] == postorder[r2])
    			{
    				root->left = dfs(inorder, l1, i - 1, postorder, l2, l2 + i - l1-1);
    				root->right = dfs(inorder, i + 1, r1, postorder, l2 + i - l1, r2 - 1);
    				return root;
    			}
    		}
    		return NULL;
        }
    };