889.根据前序和后序遍历构造二叉树

链接：889.根据前序和后序遍历构造二叉树
难度：Medium
标签：树、数组、哈希表、分治、二叉树
简介：返回与给定的前序和后序遍历匹配的任何二叉树。

题解 1 - java

• 编辑时间：2020-02-22
• 执行用时：3ms
• 内存消耗：39.4MB
• 编程语言：java
• 解法介绍：通过前序的左节点头部和后序的左节点头部进行匹配获取左节点的最大下标，再通过分割数组进行递归遍历新左节点和右节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
    	int len = pre.length;
    	if(len==0)return null;
    	TreeNode node = new TreeNode(pre[0]);
    	if(len==1)return node;
    	int L=0;
    	for(int i=0;i<len;i++)
    		if(post[i]==pre[1])
    			L=i+1;
    	node.left=constructFromPrePost(Arrays.copyOfRange(pre, 1, L+1), Arrays.copyOfRange(post, 0, L));
    	node.right=constructFromPrePost(Arrays.copyOfRange(pre, L+1, len), Arrays.copyOfRange(post, L,len-1));
    	return node;
    }
}

题解 2 - python

• 编辑时间：2024-02-23
• 执行用时：42ms
• 内存消耗：16.39MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not preorder: return None
        l = set()
        r = set()
        for i in range(len(preorder) - 1):
            l.add(preorder[i + 1])
            r.add(postorder[i])
            if l == r: break
        cnt = len(l)
        return TreeNode(
            preorder[0],
            self.constructFromPrePost(preorder[1:cnt + 1], postorder[:cnt]),
            self.constructFromPrePost(preorder[cnt + 1:], postorder[cnt:-1])
        )