代码随想录算法训练营第二十天 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236.二叉树的最近公共祖先

530.二叉搜索树的最小绝对差

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：二叉搜索树中，需要掌握如何双指针遍历！| LeetCode：530.二叉搜索树的最小绝对差

状态：AC

思路

• 思路一：二叉搜索树中序遍历是递增的，中序遍历后得到结果数组，再遍历结果数组，计算相邻元素的差，找最小值。
• 思路二：使用双指针，看了卡哥的解法豁然开朗。定义当前指针cur和上个节点的指针pre=nil
  1. cur开始中序遍历时，不断找最左节点的值
  2. 和pre指针判断，如果pre为空，说明当前是第一个节点，此后将pre=cur
  3. cur继续递归，pre始终会慢cur一层
  4. 比较cur.Val - pre.Val<minNum

代码

// 思路一
func getMinimumDifference(root *TreeNode) int {
	var path []int
	inorder(root, &path)
	minNum := math.MaxInt32
	for i := 1; i < len(path); i++ {
		if path[i]-path[i-1] < minNum {
			minNum = path[i] - path[i-1]
		}
	}
	return minNum
}

func inorder(root *TreeNode, path *[]int) {
	if root.Left != nil {
		inorder(root.Left, path)
	}
	*path = append(*path, root.Val)
	if root.Right != nil {
		inorder(root.Right, path)
	}
}

// 思路二
func getMinimumDifference(root *TreeNode) int {
	minNum := 999999999
	var pre *TreeNode
	var inorder2 func(cur *TreeNode)
	inorder2 = func(cur *TreeNode) {
		if cur == nil {
			return
		}
		inorder2(cur.Left)
		if pre != nil && cur.Val-pre.Val < minNum {
			minNum = cur.Val - pre.Val
		}
		pre = cur
		inorder2(cur.Right)
	}
	inorder2(root)
	return minNum
}

501.二叉搜索树中的众数

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数

状态：AC

思路

整体思路和上题基本类似，依旧使用双指针。只不过要多定义些变量，用来存放历史最大值maxCount，当前最大值count，众数结果maxNum

• 如果cur.Val == pre.Val，count++；
• 否则判断count与maxCount
  • count > maxCount：清空maxNum，放入新的值
  • count == maxCount：追加新的值
  • count < maxCount：不管
  • 更新count = 1

代码

func findMode(root *TreeNode) []int {
	maxCount := 0
	maxNum := []int{}
	count := 0
	var pre *TreeNode
	var mid func(cur *TreeNode)
	mid = func(cur *TreeNode) {
		if cur == nil {
			return
		}
		mid(cur.Left)
		if pre == nil {
			count = 1
		} else if pre.Val == cur.Val {
			count++
		} else {
			count = 1
		}
		pre = cur
		if count == maxCount {
			maxNum = append(maxNum, cur.Val)
		} else if count > maxCount {
			maxCount = count
			maxNum = []int{cur.Val}
		}
		mid(cur.Right)
	}
	mid(root)
	return maxNum
}

236.二叉树的最近公共祖先

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：自底向上查找，有点难度！ | LeetCode：236. 二叉树的最近公共祖先

状态：AC

思路

这道题和卡哥的思路不同。我依旧使用了中序遍历。

1. 中序遍历得到结果path
2. 查找中序遍历中p与q的位置，与root进行判断
   • 如果root在p和q的左（右）侧，root则需要向右（左）节点移动
   • 如果root在p和q之间（或root是p或q），返回即可，具体可以看下方视频

代码

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	var path []int
	getInorderPath(root, &path)
	for {
		index := 0
		indexP := 0
		indexQ := 0
		// 找到当前根结点
		for i := 0; i < len(path); i++ {
			if root.Val == path[i] {
				index = i
			}
			if p.Val == path[i] {
				indexP = i
			}
			if q.Val == path[i] {
				indexQ = i
			}
		}
		if indexP == index {
			return p
		}
		if indexQ == index {
			return q
		}
		// p,q 分散在中序遍历的根结点两侧
		if indexP < index && index < indexQ || indexQ < index && index < indexP {
			return root
		}
		// p,q 在根节点左侧
		if indexP < index && indexQ < index {
			root = root.Left
			continue
		}
		// p,q 在根节点右侧
		if index < indexP && index < indexQ {
			root = root.Right
			continue
		}

	}
}
func getInorderPath(root *TreeNode, path *[]int) {
	if root == nil {
		return
	}
	getInorderPath(root.Left, path)
	*path = append(*path, root.Val)
	getInorderPath(root.Right, path)
}