代码随想录算法训练营|day20

654.最大二叉树

(1)递归：找到数组最大值index，递归构造左右子树

func constructMaximumBinaryTree(nums []int) *TreeNode {
    if nums == nil || len(nums) == 0 {
        return nil
    }
    var help func(nums []int, left, right int) *TreeNode
    help = func(nums []int, left, right int) *TreeNode{
        if left > right {
            return nil
        }
        index := left
        for i := left; i <= right; i++ {
            if nums[i] > nums[index]  {
                index = i
            }
        }
        root := &TreeNode{Val:nums[index]}
        root.Left = help(nums, left, index - 1)
        root.Right = help(nums, index + 1, right)
        return root
    }
    return help(nums, 0, len(nums) - 1)
}

(2)单调栈
栈顶节点值大于当前节点值，当前节点直接入栈，同时维护节点关系topNode.Right = node；
否则，栈顶节点出栈并维护节点关系node.Left = topNode

func constructMaximumBinaryTree(nums []int) *TreeNode {
    if nums == nil || len(nums) == 0 {
        return nil
    }
    stack := []*TreeNode{}
    for i := 0; i < len(nums); i++ {
        node := &TreeNode{Val:nums[i]}
        for len(stack) > 0 {
            topNode := stack[len(stack) - 1]
            if topNode.Val > node.Val {
                stack = append(stack, node)
                topNode.Right = node
                break
            } else {
                stack = stack[:len(stack) - 1]
                node.Left = topNode
            }
        }
        if len(stack) == 0 {
            stack = append(stack, node)
        }
    }
    return stack[0]
}

617.合并二叉树

(1)递归

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1   
    }
    root1.Val += root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1
}

(2)迭代
当前节点左右子树都不为空，压入栈求和；否则将不空的树赋值给空树【目标返回的数】

//栈
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }
    stack := []*TreeNode{}
    stack = append(stack, root1)
    stack = append(stack, root2)
    for len(stack) > 0 {
        node2 := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        node1 := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        node1.Val += node2.Val
        if node1.Left != nil && node2.Left != nil {
            stack =append(stack, node1.Left)
            stack =append(stack, node2.Left)
        } else if node1.Left == nil {
            node1.Left = node2.Left
        }
        if node1.Right != nil && node2.Right != nil {
            stack = append(stack, node1.Right)
            stack = append(stack, node2.Right)
        } else if node1.Right == nil {
            node1.Right = node2.Right
        }
    }
    return root1
}

//队列
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1   
    }
    queue := []*TreeNode{}
    queue = append(queue, root1)
    queue = append(queue, root2)
    for len(queue) > 0 {
        node1 := queue[0]
        queue = queue[1:]
        node2 := queue[0]
        queue = queue[1:]
        node1.Val += node2.Val
        if node1.Left != nil && node2.Left != nil {
            queue = append(queue, node1.Left)
            queue = append(queue, node2.Left)
        }else if node1.Left == nil {
            node1.Left = node2.Left
        }
        if node1.Right != nil && node2.Right != nil {
            queue = append(queue, node1.Right)
            queue = append(queue, node2.Right)
        }else if node1.Right == nil {
            node1.Right = node2.Right
        }
    }
    return root1
}

700.二叉搜索树中的搜索

(1)递归

func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil || root.Val == val{
        return root
    }
    if val < root.Val {
        return searchBST(root.Left, val)
    } 
    return searchBST(root.Right, val)
}

(2)迭代：因为二叉搜索树的节点的有序性，可以不使用辅助栈或队列写出迭代法。

func searchBST(root *TreeNode, val int) *TreeNode {
    for root != nil {
        if root.Val > val{
        root = root.Left
        }else if root.Val < val{
            root = root.Right
        }else {
            return root 
        }
    }
    return nil
}

98.验证二叉搜索树

(1)递归：初始化左右边界，递归；左子树最大边界为当前节点【开区间】，右子树最小边界为当前节点【开区间】

func isValidBST(root *TreeNode) bool {
    var help func(root *TreeNode, lower, upper int) bool 
    help = func(root *TreeNode, lower, upper int) bool {
        if root == nil {
            return true
        }
        if root.Val <= lower || root.Val >= upper {
            return false
        }
        return help(root.Left, lower, root.Val) && help(root.Right, root.Val, upper)
    }
    return help(root, math.MinInt64, math.MaxInt64)
}

(2)中序遍历：二叉搜索树必为严格升序，若当前节点值小于等于前一个节点值，返回false，否则继续遍历

//递归
func isValidBST(root *TreeNode) bool {
    pre := math.MinInt64
    var help func(root *TreeNode) bool
    help  = func(root *TreeNode) bool {
        if root == nil {
            return true
        }
        if !help(root.Left) || pre >= root.Val {
            return false
        }
        pre = root.Val
        return help(root.Right)
    }
    return help(root)
}

//迭代
func isValidBST(root *TreeNode) bool {
    stack := []*TreeNode{}
    node := root 
    preVal := math.MinInt64
    for len(stack) > 0 || node != nil {
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        if  node.Val <= preVal {
            return false
        }
        preVal = node.Val
        node = node.Right
    }
    return true
}

代码随想录文章详解

654.最大二叉树
617.合并二叉树
700.二叉搜索树中的搜索
98.验证二叉搜索树

总结

搜索整棵二叉树，递归有无返回值，取决于是否需要对其进行处理
单调栈