php 解法, 执行用时: 12 ms, 内存消耗: 20.1 MB, 提交时间: 2024-02-22 10:54:21

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {

    /**
     * @param Integer[] $preorder
     * @param Integer[] $postorder
     * @return TreeNode
     */
    function constructFromPrePost($preorder, $postorder) {
        if ( $preorder == null ) return null;
        $root = new TreeNode($preorder[0]);
        
        if ( count($preorder) == 1 ) return $root;

        $l = array_search($preorder[1], $postorder) + 1;
        
        $root->left = $this->constructFromPrePost(array_slice($preorder, 1, $l), array_slice($postorder, 0, $l));
        $root->right = $this->constructFromPrePost(array_slice($preorder, $l+1), array_slice($postorder, $l, -1));
        return $root;
    }
}

golang 解法, 执行用时: 4 ms, 内存消耗: 3 MB, 提交时间: 2022-11-27 12:36:13

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
    //   中左右           左右中
    //中   左    右         左     右        中
    if len(postorder)==0{
        return nil
    }
    if len(postorder)==1{
        return &TreeNode{postorder[0],nil,nil}
    }
    root:=new(TreeNode)
    i:=0
    for i=0;i<len(postorder);i++{
        if postorder[i]==preorder[1]{
            break
        }
    }
    lenLeft:=i+1
    root.Val=preorder[0]
    root.Left=constructFromPrePost(preorder[1:1+lenLeft],postorder[:lenLeft])
    root.Right=constructFromPrePost(preorder[1+lenLeft:],postorder[lenLeft:len(postorder)-1])
    return root
}

golang 解法, 执行用时: 4 ms, 内存消耗: 2.9 MB, 提交时间: 2022-11-27 12:35:52

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {

    root := build(&preorder, &postorder, 0, len(preorder)-1, 0, len(postorder)-1)
    return root
}

// a，b分别是前序数组的左右边界，c，d是后序数组的左右边界
func build(preorder *[]int, postorder *[]int, a,b int, c,d int) *TreeNode {
    if a > b {
        return nil
    }
    root := &TreeNode{Val:(*preorder)[a],}
    if a == b {
        return root
    }
    tmp := 0 // preorder[a+1]是左子树的值，找到该值在后序数组中的索引
    for i:=c; i<=d; i++ {
        if (*postorder)[i] == (*preorder)[a+1] {
            tmp = i
        }
    }
    
    leftLength := tmp - c + 1 //求出左子树长度
    root.Left = build(preorder, postorder, a+1, a+leftLength, c, c + leftLength-1)
    root.Right = build(preorder, postorder, a+leftLength+1, b, c + leftLength, d-1)
    return root
}

python3 解法, 执行用时: 48 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-27 12:35:03

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def constructFromPrePost(self, pre, post):
        def make(i0, i1, N):
            if N == 0: return None
            root = TreeNode(pre[i0])
            if N == 1: return root

            for L in range(N):
                if post[i1 + L - 1] == pre[i0 + 1]:
                    break

            root.left = make(i0 + 1, i1, L)
            root.right = make(i0 + L + 1, i1 + L, N - 1 - L)
            return root

        return make(0, 0, len(pre))

python3 解法, 执行用时: 32 ms, 内存消耗: 15.2 MB, 提交时间: 2022-11-27 12:34:31

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def constructFromPrePost(self, pre, post):
        def dfs(pre,post):
            if not pre:
                return None
            # 数组长度为1时，直接返回即可
            if len(pre)==1:
                return TreeNode(pre[0])
            # 根据前序数组的第一个元素，创建根节点     
            root = TreeNode(pre[0])
            # 根据前序数组第二个元素，确定后序数组左子树范围
            left_count = post.index(pre[1])+1
            # 递归执行前序数组左边、后序数组左边
            root.left = dfs(pre[1:left_count+1],post[:left_count])
            # 递归执行前序数组右边、后序数组右边
            root.right = dfs(pre[left_count+1:],post[left_count:-1])
            # 返回根节点
            return root
        return dfs(pre,post)

python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-27 12:33:44

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def constructFromPrePost(self, pre, post):
        if not pre: return None
        root = TreeNode(pre[0])
        if len(pre) == 1: return root

        L = post.index(pre[1]) + 1
        root.left = self.constructFromPrePost(pre[1:L+1], post[:L])
        root.right = self.constructFromPrePost(pre[L+1:], post[L:-1])
        return root