二叉树的最近公共祖先

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

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

递归回溯

1.若root中只包含p则返回p
2.若root中只包含q则返回q
3.若root中不包含p也不包含q则返回NULL
5.若root中同时包含p和q，则返回root（此时root为最近公共祖先）

/**
 * 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 || p == root || q == root {
		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
}

for循环

记录父节点

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// 父节点路径
    parent := map[int]*TreeNode{}
    // 访问路径
    visited := map[int]bool{}
    // 遍历树
    var dfs func(*TreeNode)
    dfs = func(r *TreeNode) {
        if r == nil {
            return
        }
        // 只看左右节点，因为只记录父节点
        if r.Left != nil {
            parent[r.Left.Val] = r
            dfs(r.Left)
        }
        if r.Right != nil {
            parent[r.Right.Val] = r
            dfs(r.Right)
        }
    }
    dfs(root)

    // 记录节点的访问路径，从下向上
    for p != nil {
        visited[p.Val] = true
        p = parent[p.Val]
    }
    // 看另一节点是否有相同值，有则返回就是结果
    for q != nil {
        if visited[q.Val] {
            return q
        }
        q = parent[q.Val]
    }

    return nil
}