4

LeetCode分类总结 - BST(搜索二叉树)

 2 years ago
source link: https://dinghaoli.github.io/2019/04/LC_BST/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

LeetCode分类总结 - BST(搜索二叉树)

calendar.png2019-04-18 | 阅读：次

LeetCode分类总结 - BST(搜索二叉树)

本文的题目分类来自于花花酱 LeetCode 题目分类。在做题的过程中加入了自己的总结和归纳。

98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than the node’s key. Both the left and right subtrees must also be binary search trees.

解题思路就是利用BST的基础特性：InOrder顺序就为从小到大的顺序。

  • root.Left中所有节点的最大值小于root.Val
  • root.Right中所有节点的最小值大于root.Val

所以，在一开始设置int64的最大最小 math.MaxInt64 math.MinInt64 作为边界即可。

// 易错点：
// 左右子树的最大最小值传递
// 判断时需要绝对大于/小于 root.Val > min && root.Val < max
func isValidBST(root *TreeNode) bool {
    var isValid func(int,int,*TreeNode) bool
    isValid = func(max, min int, root *TreeNode) bool {
        if root == nil {
            return true
        }
        return root.Val > min && root.Val < max  &&
        // root.Left中左右节点的最大值小于root.Val
        isValid(root.Val,min,root.Left) && 
        // root.Right中左右节点的最小值大于root.Val
        isValid(max,root.Val,root.Right)
    }
    max := math.MaxInt64
    min := math.MinInt64
    return isValid(max, min, root)
}

530. Minimum Absolute Difference in BST

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

与上一题类似，利用BST的特征，中序遍历，在遍历过程中缓存元素并且比较相邻两个元素

func getMinimumDifference(root *TreeNode) int {
    res := []int{}
    min := math.MaxInt64
    var inOrder func(*TreeNode)
    inOrder = func(root *TreeNode) {
        if root == nil {
            return 
        }
        inOrder(root.Left)
        res = append(res, root.Val)
        if len(res) > 1 && res[len(res)-1] - res[len(res)-2] < min {
            min = res[len(res)-1] - res[len(res)-2]
        }
        inOrder(root.Right)
    }
    inOrder(root)
    return min
}

700. Search in a Binary Search Tree

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

依旧是根据BST特性, 有二分搜索的效果，因为比root小的元素全部在root.Left，比root大的元素全部在root.Right

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

701. Insert into a Binary Search Tree

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

不需要平衡，只需要插入，所以用BST的特性+递归，遇到空就直接插入就好了，这里使用原函数的递归可以减少代码量。

func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return &TreeNode{
			Val: val,
		}
	}

	if root.Val <= val {
		root.Right = insertIntoBST(root.Right, val)
	} else {
		root.Left = insertIntoBST(root.Left, val)
	}

	return root
}

230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

本质上还是使用BST的中序遍历特性，只是要注意，所有递归过程中共享一个变量k，用于计数是否遍历到第K个元素。在golang可以使用闭包来完成。注意考虑找到函数后如何尽快跳出递归（可以用一个共享flag）。

func kthSmallest(root *TreeNode, k int) int {
    found := false
    res := 0
    var inOrder func(*TreeNode)
    inOrder = func(root *TreeNode){
        if root == nil || found == true {
            return
        }
        inOrder(root.Left)
        if k == 1 {
            res = root.Val
            found = true
            k--
            return
        }
        k--
        inOrder(root.Right)
    }
    inOrder(root)
    return res
}

99. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

还是利用BST中序遍历的特性，但是得考虑两种乱序的情况，

  • 如果要调整 [1, 2, 6, 4, 5, 3, 7] 中错位的 6 和 3，其实是把 [6, 4] 中的较大值与 [5, 3] 中的较小值交换。这时，有两组错序。
  • 还有可能是 [1, 3, 2] 中错位的 3 和 2，只有一组错序的 [3, 2]

所以需要兼容以上两种情况：root表示当前节点，prev表示前一个节点（如果有的话），first表示第一个乱序的节点，second表示第二个乱序的节点。在中序遍历种找乱序的节点。具体解释看下方代码和注释

func recoverTree(root *TreeNode) {
    if root == nil {
        return
    }
    var first, second, prev *TreeNode
    var inOrder func(*TreeNode)
    inOrder = func(root *TreeNode){
        if root == nil {
            return
        } 
        inOrder(root.Left)
        // 判断是否已经出现了乱序的情况
        if prev != nil && prev.Val > root.Val {
			// 如果要调整 [1, 2, 6, 4, 5, 3, 7] 中错位的 6 和 3
			// 其实是把 [6, 4] 中的较大值与 [5, 3] 中的较小值交换。这时，有两组错序。
			// 但是，还有可能是
			// [1, 3, 2] 中错位的 3 和 2，只有一组错序的 [3, 2]
			// 以下的两个 if 语句，可以兼容以上两种情况
           // 
           // first为空，说明第一次遇到了逆序
           // 让first等于prev
			if first == nil {
				first = prev
			}
           // 说明first已经被占，先让second设为第一组的乱序的后面那个元素
           // 如果继续往下迭代，如果遇到第二个乱序点，也会更新second。
			if first != nil {
				// 当存在第二组错序的时候
				// second 的值，会被修改
				second = root
			}
		}
        prev = root
        inOrder(root.Right)
    }
    inOrder(root)
    if first != nil && second != nil {
        first.Val, second.Val = second.Val, first.Val
    }
    return 
}

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

关键点在于递归调用，自己本身递归，不用写匿名函数。根据排序的特性，每次都去中间元素mid来构建root，然后左右分别用子数组递归实现。

func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    mid := len(nums)/2
    root := &TreeNode{nums[mid], nil, nil}
    root.Left =  sortedArrayToBST(nums[:mid])
    root.Right =  sortedArrayToBST(nums[mid+1:])
    return root
}

501. Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
  • Both the left and right subtrees must also be binary search trees.

算法一： 把数组遍历一遍，把数量存在map中，之后在遍历map，设置一个max，如果一个数出现max次就直接加入结果集，如果出现大于max次，那就清空结果集再加入结果集，但是这个算法没用到BST性质而且满慢，因为还需要遍历map

算法二： 一次过：在inorder遍历过程中（相同的元素会连续出现），所以我们可以同时计数，比较，替换，注意处理头尾情况，这个流程控制比较复杂，但是速度会快一些。

算法一实现：

// Runtime: 12 ms, faster than 72.00% of Go online submissions for Find Mode in Binary Search Tree.
// Memory Usage: 6.2 MB, less than 50.00% of Go online submissions for Find Mode in Binary Search Tree.

func findMode(root *TreeNode) []int {
	r := map[int]int{}
    var search func(root *TreeNode) 
    search = func (root *TreeNode) {
	    if root == nil {
		    return
	    }
	    r[root.Val]++
	    search(root.Left)
	    search(root.Right)
    }
	search(root)

	max := -1
	res := []int{}
	for n, v := range r {
		if max <= v {
			if max < v {
				max = v
				res = res[0:0]
			}
			res = append(res, n)
		}
	}

	return res
}

450. Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

  • Search for a node to remove.
  • If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

二分搜索寻找key + 递归处理key节点 + 递归处理旁枝

  • 原函数递归, 如果root.Val大于key，那就让左边处理root.Left = deleteNode(root.Left, key)，否则让有右边处理，最后返回root
  • 如果root.Val等于key，那我们规定把左边的点递上来:
    • 如果root没有左叶子，那么直接返回root的右叶子，因为root需要被删除
    • 如果root的左叶子存在：
      • 如果root的右叶子不存在，那么直接返回root的左叶子
      • 存储root.Left.Right到tmp, 然后让root.Left.Right = root.Right，最后在root.Right 中插入 tmp，由BST特性可知，tmp中所有数肯定小于root.Right，所以执行insertMin(root.Right, tmp), 递归找到root.Right的最左侧，插入即可。
// Runtime: 356 ms, faster than 80.43% of Go online submissions for Delete Node in a BST.
// Memory Usage: 316.9 MB, less than 15.38% of Go online submissions for Delete Node in a BST.
func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == key {
        if root.Left == nil {
            return root.Right
        } else {
            if root.Right == nil {
                return root.Left
            }
            tmp := root.Left.Right
            root.Left.Right = root.Right
            insertMin(root.Right, tmp)
            return root.Left
        } 
    } else if root.Val < key {
        root.Right = deleteNode(root.Right, key)
        return root
    }
    root.Left = deleteNode(root.Left, key)
    return root
}

func insertMin(root *TreeNode, min *TreeNode){
    if min == nil || root == nil {
        return 
    }
    if root.Left == nil {
        root.Left = min
        return
    }
    insertMin(root.Left, min)
}
  • 掌握BST的结构特性非常重要：
    • BST的InOrder顺序就为BST元素从小到大的顺序。
    • root.Left中所有节点的最大值小于root.Val，root.Right中所有节点的最小值大于root.Val，根据BST特性, 有二分搜索的效果，因为比root小的元素全部在root.Left，比root大的元素全部在root.Right
    • 树的递归结构
  • 优先使用原函数（单个目标函数）自身递归，实在不行采用匿名函数或外加递归函数。能用自己本身递归最方便。
  • 注意在BST中的遍历为递归性质，所以需要考虑递归的开始/结束条件，可以通过共享公共变量来设置flag让递归减少计算量
  • 注意递归的特性，需要迭代的值可以用递归时参数传递，如果是需要共享的参数，需要全局定义/使用闭包

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK