算法刷题笔记 (11) 最小栈 二叉树的直径 二叉搜索树

最小栈

最小栈

解题思路

利用一个辅助栈，用来记录当前已压栈元素中的最小元素。在进行压栈操作时，不仅更新数据栈，还要更新辅助栈。其中，辅助栈的更新策略：

• 如果当前压栈元素小于辅助栈的栈顶元素，则将当前压栈元素压入辅助栈
• 否则，将辅助栈的栈顶元素再一次压入辅助栈中

解题代码

type MinStack struct {
    data []int  // 数据栈
    aux []int   // 辅助栈
    top int // 栈顶指针
}


func Constructor() MinStack {
    return MinStack{
        data: []int{},
        aux: []int{},
        top: -1,
    }
}


func (this *MinStack) Push(val int)  {
    // 数据压入数据栈
    this.data = append(this.data, val)
    // 压入辅助栈
    if this.top == -1 ||  val < this.aux[this.top]{
        // 辅助栈空栈，直接入栈
        // 或者当前压栈元素小于最小元素，辅助栈压入当前元素
        this.aux = append(this.aux, val)
        
    } else {
        // 重新压入辅助栈栈顶元素
        this.aux = append(this.aux, this.aux[this.top])
    }
    // 修改栈顶指针
    this.top++  
}


func (this *MinStack) Pop()  {
    // 数据栈辅助栈均弹出栈顶
    this.data = this.data[:this.top]
    this.aux = this.aux[:this.top]
    this.top--
}


func (this *MinStack) Top() int {
    return this.data[this.top]  // 返回数据栈顶元素
}


func (this *MinStack) GetMin() int {
    return this.aux[this.top]   // 返回最小值
}

二叉树的直径

二叉树的直径

解题思路

利用二叉树的后序遍历，用一个变量max记录两个节点之间的最大路径长度，分别计算左右子树深度left和right，其中left+right为以当前节点为根的二叉树的最大路径长度，若left+right > max，则更新max。后序遍历返回max(left, right)

解题代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
    var max int // 记录两节点之间的最大路径（直接）
    var postorder func(root *TreeNode) int
    postorder = func(root *TreeNode) int {
        if root != nil {
            var left, right int// 左右子树深度
            if root.Left != nil {
                left = postorder(root.Left) +1  // 计算左子树深度
            }
            if root.Right != nil {
                right = postorder(root.Right)+1    // 计算右子树深度
            }
            if left + right > max {
                // 更新两节点的最大路径
                max = left + right
            }
            // 返回左右子树中深度较大的值
            if left > right {
                return left
            } else {
                return right
            }
        }
        return 0
    }
    postorder(root)
    return max
}

二叉搜索树

验证二叉搜索树

解题思路

对二叉树进行中序遍历，若遍历序列是严格单调递增的，那么就是二叉搜索树；否则不是二叉搜索树

解题代码

中序遍历 - 递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    flag := true    // 标记是否是二叉搜索树
    lastVisit := math.MinInt64  // 上一个访问的节点
    var inorder func(root *TreeNode)

    inorder = func(root *TreeNode) {
        if root != nil {
            inorder(root.Left)
            if root.Val <= lastVisit {
                // 中序遍历序列不是递增的，则不是二叉搜索树
                flag = false
            }
            lastVisit = root.Val
            inorder(root.Right)
        }
    }
    inorder(root)

    return flag
}

中序遍历 - 非递归

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    lastVisit := math.MinInt64
    stack := make([]*TreeNode, 0)   // 栈
    cur := root // 遍历指针

    for len(stack) > 0 || cur != nil {
        for cur != nil {
            // 当前节点入栈，进入左子树
            stack = append(stack, cur)
            cur = cur.Left
        }
        if len(stack) > 0 {
            // 访问当前栈顶节点
            cur = stack[len(stack)-1]
            if cur.Val <= lastVisit {
                // 遍历序列不严格递增，不是二叉搜索树，直接返回false
                return false
            }
            lastVisit = cur.Val
            // 弹出栈顶
            stack = stack[:len(stack)-1]
            // 进入右子树
            cur = cur.Right
        }
    }

    // 遍历序列严格递增，是二叉搜索树
    return true
}