Tree树 - 二叉搜索树 - 《leetcode之路》

原理
结构
性质
- 二叉搜索树的最近公共祖先

二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：

每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

二叉搜索树的有优点是，即便在最坏的情况下，也允许你在O(h)的时间复杂度内执行所有的搜索、插入、删除操作。

原理

二叉搜索树（BST）又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。一般地，除了key和卫星数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。如果某个孩子结点或父结点不存在，则相应属性的值为空（NIL）。根结点是树中唯一父指针为NIL的结点，而叶子结点的孩子结点指针也为NIL

结构

二叉搜索树是能够高效地进行如下操作的数据结构。
1.插入一个数值
2.查询是否包含某个数值
3.删除某个数值

性质

设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key≤x.key。如果y是x右子树中的一个结点，那么y.key≥x.key。
在二叉搜索树中：
1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3.任意结点的左、右子树也分别为二叉搜索树

二叉搜索树验证
**
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
2
/ \
1 3
输出: true**

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
//递归
func isValidBST(root *TreeNode) bool {
    return helper(root,math.MinInt64,math.MaxInt64)
}
func helper(root *TreeNode,min,max int) bool {
    if root == nil {
        return true 
    }
    if root.Val <= min || root.Val >= max {
        return false 
    }
    return helper(root.Left,min,root.Val) && helper(root.Right,root.Val,max)
}
// 迭代 
//思路和算法
//基于方法一中提及的性质，我们可以进一步知道二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，
//这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。
//如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是，下面的代码我们使用栈来模拟中序遍历的过程
func isValidBST(root *TreeNode) bool {
    if root == nil {
        return true 
    }
    res := inorder(root)
    for i:=0;i<len(res)-1;i++ {
        if res[i] >= res[i+1] {
            return false 
        }
    }
    return true 
}
func inorder(root *TreeNode) []int {
    res := []int{}
    if root == nil {
        return res 
    }
    res = append(res,inorder(root.Left)...)
    res = append(res,root.Val)
    res = append(res,inorder(root.Right)...)
    return res 
}

二叉搜索树查找
**
根据BST的特性，对于每个节点：
如果目标值等于节点的值，则返回节点；
如果目标值小于节点的值，则继续在左子树中搜索；
如果目标值大于节点的值，则继续在右子树中搜索。

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
例如，
给定二叉搜索树:
        4
       / \
      2   7
     / \
    1   3
和值: 2
-------------------------------------------
你应该返回如下子树:
      2     
     / \   
    1   3

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 递归 
func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return nil 
    }
    if root.Val > val {
        return searchBST(root.Left,val)
    }
    if root.Val < val {
        return searchBST(root.Right,val)
    }
    return root 
}
// 迭代
func searchBST(root *TreeNode, val int) *TreeNode {
    for root != nil {
        if root.Val ==  val {
            return root 
        }
        if root.Val < val {
            root = root.Right 
        } else {
            root = root.Left  
        }
    } 
    return root 
}

二叉搜索树插入
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果

输入：root = [4,2,7,1,3], val = 5输出：[4,2,7,1,3,5]解释：**另一个满足题目要求可以通过的树是：二叉搜索树 - 图1

/**
 * 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 root.Val > val {
        root.Left = insertIntoBST(root.Left,val)
    } else {
        root.Right = insertIntoBST(root.Right,val)
    }
    return root 
}
func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    p := root
    for p != nil {
        if val < p.Val {
            if p.Left == nil {
                p.Left = &TreeNode{Val: val}
                break
            }
            p = p.Left
        } else {
            if p.Right == nil {
                p.Right = &TreeNode{Val: val}
                break
            }
            p = p.Right
        }
    }
    return root
}

二叉搜索树删除
**
删除要比我们前面提到过的两种操作复杂许多。有许多不同的删除节点的方法，这篇文章中，我们只讨论一种使整体操作变化最小的方法。我们的方案是用一个合适的子节点来替换要删除的目标节点。根据其子节点的个数，我们需考虑以下三种情况：

如果目标节点没有子节点，我们可以直接移除该目标节点。
2. 如果目标节只有一个子节点，我们可以用其子节点作为替换。
3. 如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点

1：目标节点没有子节点
二叉搜索树 - 图2

例 2：目标节只有一个子节点
二叉搜索树 - 图3

例 3：目标节点有两个子节点
二叉搜索树 - 图4

/**
 * 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 root 
    }
    if root.Val > key {
        root.Left = deleteNode(root.Left,key)
    }  else if root.Val < key {
        root.Right = deleteNode(root.Right,key)
    } else {
        if root.Left == nil {
            return root.Right 
        }
        if root.Right == nil {
            return root.Left 
        }
        maxNode := findMax(root.Right)
        root.Val = maxNode.Val 
        root.Right = deleteNode(root.Right,root.Val)
    }
    return root 
}
func findMax(node *TreeNode) *TreeNode {
    for node.Left != nil {
        node = node.Left 
    }
    return node 
}

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
二叉搜索树 - 图5


/**
 * 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 root 
    }
    if root == p || root == q {
        return root }
    left := lowestCommonAncestor(root.Left,p,q)
    right := lowestCommonAncestor(root.Right,p,q)
    if left == nil {
        return right 
    }
    if right == nil {
        return left 
    }
    return root 
}
//迭代 
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    node :=  root 
    for node != nil {
        if p.Val < node.Val && q.Val < node.Val {
            node = node.Left
        } else if p.Val > node.Val && q.Val > node.Val {
            node = node.Right 
        } else  {
            return node 
        }
    }
    return node 
}