公共祖先节点

1. 题目描述

给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

2. 思路

• 同二叉树的最近公共祖先.md一样，只不过这里q和p是int val而不是*TreeNode node

1. 思路一
   • 树中的任意两个节点肯定有公共祖先节点，再怎么也得有个root是公共的。
   • 而只要有公共祖先节点，那么DFS路径上必然会有重复的节点，从后往前找出该数即可
2. 思路二
   • 递归

3. 实现

3.1. DFS路径

//空间：O(N)
//时间：O(N)
func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int {
	if root == nil {
		return 0
	}

	path1 := make([]int, 0)
	path1Flag := findPath(root, o1, &path1)

	path2 := make([]int, 0)
	path2Flag := findPath(root, o2, &path2)

	if !path1Flag || !path2Flag {
		return 0
	}

	count := 0
	if len(path1) > len(path2) {
		path1 = path1[:len(path2)]
		count = len(path2)
	} else {
		path2 = path2[:len(path1)]
		count = len(path1)
	}

	for i := count - 1; i >= 0; i-- {
		if path1[i] == path2[i] {
			return path1[i]
		}
	}

	return 0
}

func findPath(root *TreeNode, data int, path *[]int) bool {
	if root == nil {
		return false
	}

	*path = append(*path, root.Val)
	if root.Val == data {
		return true
	}
	flag := findPath(root.Left, data, path)
	if flag {
		return flag
	}
	flag = findPath(root.Right, data, path)
	if flag {
		return flag
	}
	*path = (*path)[:len(*path)-1]
	return false
}

3.2. 递归

//时间：O（N）
//空间：O(h)，最坏 O(N)
func lowestCommonAncestor2(root *TreeNode, o1 int, o2 int) int {
	return commonAncestor(root, o1, o2).Val
}

func commonAncestor(root *TreeNode, o1 int, o2 int) *TreeNode {
	if root == nil || root.Val == o1 || root.Val == o2 {
		return root
	}

	left := commonAncestor(root.Left, o1, o2)
	right := commonAncestor(root.Right, o1, o2)

	if left == nil {
		return right
	}
	if right == nil {
		return left
	}

	return root

}

4. 参考

• 在二叉树中找到两个节点的最近公共祖先_牛客题霸_牛客网