二叉树的最近公共祖先

1. 题目描述

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

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

2. 思路

1. 思路一
   • DFS找到包含该节点的路径，然后从后往前找到相同的节点即为公共祖先
2. 思路二
   1. 递归

3. 实现

3.1. DFS

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	path1 := make([]*TreeNode, 0)
	if flag := lowestCommonAncestorDFS(root, p, &path1); !flag {
		return nil
	}

	path2 := make([]*TreeNode, 0)
	if flag := lowestCommonAncestorDFS(root, q, &path2); !flag {
		return nil
	}

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

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

	return nil
}

func lowestCommonAncestorDFS(root *TreeNode, find *TreeNode, path *[]*TreeNode) bool {
	if root == nil {
		return false
	}

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

3.2. 递归

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 && right != nil {
        return root
    }else if left == nil {
        return right
    }else if right == nil {
        return left
    }
    return nil
}

4. 参考

• 236. 二叉树的最近公共祖先 - 力扣（LeetCode）
• 236. 二叉树的最近公共祖先（DFS ，清晰图解） - 二叉树的最近公共祖先 - 力扣（LeetCode）
• 【C++ 经典递归】思路非常好理解 时间复杂度O(n), 空间复杂度O(n) - 二叉树的最近公共祖先 - 力扣（LeetCode）