剑指offer 重建二叉树

占用空间太大


func reConstructBinaryTree( pre []int ,  vin []int ) *TreeNode {
	// write code here
	if len(pre)==0{
		return nil
	}
	var left_pre, right_pre,left_vin,right_vin []int
	var root = &TreeNode{pre[0], nil, nil}
	var root_son = 0
	for i:=0;i<len(vin);i++{
		if vin[i] == pre[0]{
			root_son = i
            break
		}
	}
	for i:=0; i < root_son; i++{
		left_vin = append(left_vin, vin[i])
		left_pre = append(left_pre, pre[i+1])
	}
	for i:=root_son+1; i<len(vin); i++{
		right_vin = append(right_vin, vin[i])
		right_pre = append(right_pre, pre[i])
	}

	root.Left = reConstructBinaryTree(left_pre,left_vin)
	root.Right = reConstructBinaryTree(right_pre,right_vin)
	return root
}



第二种写法,差不多,没第一个好想

func rebuild(pre []int, pre_left int, pre_right int , vin []int, vin_left int, vin_right int)*TreeNode {
    if (pre_left > pre_right){
        return nil
    }
    var root = &TreeNode{pre[pre_left], nil, nil}
    for i:= vin_left;i<=vin_right;i++{
        if vin[i] == root.Val{
            root.Left = rebuild(pre, pre_left+1, pre_left+i-vin_left,vin,vin_left,i-1)
            root.Right = rebuild(pre,pre_left+i-vin_left+1,pre_right,vin,i+1,vin_right)
        }
    }
    return root
}
func reConstructBinaryTree( pre []int ,  vin []int ) *TreeNode {
	// write code here
    return rebuild(pre,0,len(pre)-1,vin,0,len(vin)-1)
}

发表评论 / Comment

用心评论~