[代码随想录]Day19-二叉树part08

题目：235. 二叉搜索树的最近公共祖先

思路：

BST和普通二叉树不同的一点是可以根据特性来找最近公共祖先，只要找到第一个值比p大比q小(假设p<q)的节点返回即可。

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val   int
 *     Left  *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    if p.Val > q.Val {
        p, q = q, p
    } // 保证p < q 范围取(p,q)
    return step(root,p,q)
}
func step(root, p, q *TreeNode) *TreeNode{
    if root == nil {
        return nil
    }
    if root.Val > q.Val { // 大于q，向左找
        left := step(root.Left, p, q)
        if left != nil {
            return left
        }
    }
    if root.Val < p.Val { // 小于p，向右找
        right := step(root.Right, p, q)
        if right != nil {
            return right
        }
    }
    return root //  现在是大于p 小于q，返回
}

参考：

代码随想录

题目：701. 二叉搜索树中的插入操作

思路：

BST的插入只需要找到第一个：

1. 比val大且没有左子树的位置
2. 比val小且没有右子树的位置

之后在该位置插入节点，向上递归返回即可。

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil { // 如果是空插入
        return &TreeNode{Val:val,}
    }
    if val < root.Val { // 向左找，找到后返回
        root.Left = insertIntoBST(root.Left, val)
        return root
    }
    if val > root.Val { // 向右找，找到后返回
        root.Right = insertIntoBST(root.Right, val)
        return root
    }
    return nil
}

参考：

代码随想录

题目：450. 删除二叉搜索树中的节点

思路：

和上一题类似，这一题要先找到值为key的节点位置，然后把该节点的左子树放到右子树的最左下角。

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if key < root.Val {
        root.Left = deleteNode(root.Left, key)
        return root
    }
    if key > root.Val {
        root.Right = deleteNode(root.Right, key)
        return root
    }
    // 下面是key == root.Val的情况
    if root.Right == nil {
        return root.Left
    }
    if root.Left == nil {
        return root.Right
    }
    left := root.Left // 记录删除节点左子树
    right := root.Right // 记录删除节点右子树
    root = root.Right // 进入右子树
    for root.Left != nil { // 找到最左侧节点
        root = root.Left
    }
    root.Left = left // 把左子树放到这里
    return right // 返回记录的右子树
}

参考：

代码随想录