网站首页

剑指offer 重建二叉树

发布时间:2021-3-1 15:00 Monday编辑:admin阅读(372)

    占用空间太大


    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)
    }