题解 | #在二叉树中找到两个节点的最近公共祖先#

package main
import (
    "math"
)
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 
 * @param root TreeNode类 
 * @param o1 int整型 
 * @param o2 int整型 
 * @return int整型
*/
func lowestCommonAncestor( root *TreeNode ,  o1 int ,  o2 int ) int {
    node := root
    num1, num2 := o1, o2
	if node == nil {
		return -1
	}
	parent := make(map[int]int, 0)
	floor := make([]*TreeNode, 0)
	floor = append(floor, node)
	//【重点】记录根节点
	parent[node.Val] = math.MinInt
	//层序遍历
	for len(floor) != 0 {
		size := len(floor)
		tmp := make([]*TreeNode, 0)
		for i := 0; i < size; i++ {
			curr := floor[0]
			floor = floor[1:]
			if curr.Left != nil {
				parent[curr.Left.Val] = curr.Val
				tmp = append(tmp, curr.Left)
			}
			if curr.Right != nil {
				parent[curr.Right.Val] = curr.Val
				tmp = append(tmp, curr.Right)
			}
		}
		floor = tmp
	}
	//从map获取num1所有父节点的路径
	ancestor := make(map[int]int, 0)
	for _, ok := parent[num1]; ok; num1, ok = parent[num1] {
		ancestor[num1] = num1
	}
	//计算最近的公共父节点：ancestor中不包含这个num2的父节点，则继续向上遍历parent中num2的父节点，肯定有一个是符合的
	var res int
	var ok bool
	for res, ok = ancestor[num2]; !ok; res, ok = ancestor[num2] {
		num2 = parent[num2]
	}
	return res
}